HK1143873B

HK1143873B - Methods and systems for providing efficient provisioning of data flows

Info

Publication number: HK1143873B
Application number: HK10110190.5A
Authority: HK
Inventors: Scott R. Kotrla; Christopher N. Del Regno; Matthew W. Turlington; Michael U. Bencheck; Richard C. Schell
Original assignee: Verizon Patent And Licensing Inc.
Priority date: 2007-10-26
Filing date: 2008-10-27
Publication date: 2013-11-29

Description

Method and system for providing efficient provisioning of data streams

Background

Traffic engineers (traffic) monitor data throughput on network devices such as routers and switches. In many cases, network devices may be oversubscribed (oversubscription) in an attempt to improve data throughput. Oversubscription may refer to a situation where a network provider provides more bandwidth to customers than a network device can provide based on a low likelihood that all customers will use the bandwidth they purchase at the same time. In conventional systems, an oversubscription factor is statically assigned to each interface of a network device based on the experience of a traffic engineer. For example, the interface of a network device may be set to a bandwidth of 1 gigabit per second (1Gbps) with an oversubscription factor of 2: 1, which allows provisioning (to provisioning) of up to 2Gbps of bandwidth on the interface.

Drawings

The objects and advantages of the exemplary embodiments will be apparent to those skilled in the art from the following detailed description taken in conjunction with the accompanying drawings, in which like reference numerals are used to designate like elements, and in which:

FIG. 1 illustrates a system for providing efficient provisioning of data streams in accordance with an exemplary embodiment;

FIG. 2 illustrates a method for new flow provisioning in accordance with an exemplary embodiment;

FIG. 3 illustrates a method for deleting provisioned flows in accordance with an example embodiment; and

fig. 4 illustrates a link aggregation environment with multiple links between network elements, according to an example embodiment.

These and other embodiments and advantages will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the various exemplary embodiments.

Detailed Description

Systems and methods according to example embodiments may include: receiving a new flow request for requesting provisioning of a flow between a computer and a server; identifying a path of one or more network elements between the computer and the server; and determining whether provisioning a flow between the computer and the server violates a restriction. The system and method may further include: updating an oversubscription factor for an interface of each of the one or more network elements without violating a constraint; and, in the event that the constraint is violated, determining whether a second path exists between the computer and the server.

The following description describes servers, computers, and network elements that may include one or more modules, some of which are explicitly shown in the figures, others of which are not shown. It is to be appreciated that the term "module" as used herein refers to computing software, firmware, hardware, and/or various combinations thereof. Note that the modules are exemplary. Modules may be combined, integrated, separated, and/or duplicated to support various applications. Further, functions described herein as being performed at a particular module may be performed at one or more other modules and/or by one or more other devices in place of, or in addition to, functions performed at the particular module. Moreover, the modules may be implemented on multiple devices and/or other components, either proximate or remote from each other. In addition, a module may be removed from one device and added to another device, and/or may be included in both devices. It is also noted that the software described herein may be tangibly embodied in one or more physical media, such as, but not limited to, a Compact Disc (CD), a Digital Versatile Disc (DVD), a floppy disk, a hard drive, Read Only Memory (ROM), Random Access Memory (RAM), and other physical media capable of storing software, and/or combinations thereof. Moreover, the figures illustrate the various components (e.g., servers, network elements, computers, etc.) separately. The functions described as being performed at the various components may be performed at other components and the various components may be combined and/or separated. Other modifications may also be made.

FIG. 1 illustrates a system for providing efficient provisioning of data streams according to an exemplary embodiment. The system 100 may provide intelligent oversubscription of data flows on network elements. The system 100 may adjust the oversubscription factor of the interfaces of the network elements to add and remove flows on the network elements to reduce the likelihood of data loss, reduce data latency (latency), and improve link utilization. In one exemplary embodiment, a flow may be an amount of bandwidth provisioned for data traffic between two devices purchased by a customer from a network provider. A flow may transport data such as, but not limited to, Internet Protocol (IP) packets, ethernet frames, pseudowires, or any data that may be transported over a telecommunications network.

For example, a customer may purchase 10 megabits per second of bandwidth on a network between a computer and a server. Without overbooking, the amount of bandwidth allocated to the client would be 10 megabits of bandwidth per second, regardless of how much bandwidth the client actually uses at any time. In general, a customer may purchase a certain amount of bandwidth in an amount that is reasonably expected to be able to be used at least under normal operating conditions. However, limiting access to this bandwidth and not oversubscribing may result in low utilization of network elements. The system 100 according to an example embodiment may improve utilization of network elements by efficiently and dynamically adjusting the oversubscription factor while minimizing latency and packet loss.

In an example embodiment, system 100 may include one or more computers 102-1, 102-2, a. The system 100 may provision flows between the computer 102 and the server 104 over a set of network elements 108 forming a network. Network element 108 may be a router, a switch, other device capable of communicating data over a network, and/or combinations thereof. Each network element 108 may include one or more interfaces that may transport data traffic at a particular rate. In one exemplary embodiment, the interface may be a multiprotocol label switching (MPLS) interface capable of providing a predetermined amount of bandwidth per second for data communications. The network elements 108 may communicate with each other, the computer 102, and the server 104 using wired and/or wireless links 112, which wired and/or wireless links 112 are communicatively coupled to interfaces of the network elements 108.

Note that each link in fig. 1 is depicted as a single line, but each line may represent one or more links for communicating data between computer 102, network element 108, server 104, Operations Support System (OSS)106, and/or a combination thereof. The Operations Support System (OSS)106 may be a provisioning server or other device capable of managing and provisioning streams over a network. The server 104 may be a communication server for communicating data with the computer 102.

Note that system 100 illustrates a simplified view of the various components included in the communication system, and that other hardware devices and software not depicted may be included in system 100. Also note that system 100 illustrates only a single Operations Support System (OSS)106 and three network elements 108. It will be appreciated that multiple instances of these devices may be used. Also, Operations Support Systems (OSSs) 106 and servers 104 may be combined. Moreover, system 100 may include other devices not shown in FIG. 1.

The system 100 may statistically multiplex data received at the network element 108 from the computer 102 and/or the server 104 over the link for communication through the network element 108. For example, network element 108-1 may receive data from each of computers 102-1 through 102-x, may multiplex the received data, and may transmit the multiplexed data over link 112-1. Before reaching the destination, the network element 108 may demultiplex the multiplexed data and may transmit the demultiplexed data to the appropriate server 104. For example, computer 102-1 may exchange data with server 104-1, and computer 102-2 may exchange data with server 104-2. Network element 108-1 may receive data from computers 102-1 and 102-2, may multiplex the data from respective computers 102-1 and 102-2, and may transmit the multiplexed data over link 112-1. Network element 108-3 may receive multiplexed data via network element 108-2 and link 112-2. Network element 108-3 may demultiplex the multiplexed data for transmission to servers 104-1 and 104-2, respectively. Data from computer 102-1 may be demultiplexed and may be transmitted to server 104-1, and data from computer 102-2 may be demultiplexed and may be transmitted to server 104-2.

In many instances, the system 100 may oversubscribe the interfaces of the network elements 108 to improve network utilization at the network elements 108. Statistical multiplexing is based on the expected low probability that all computers 102 and servers 104 on the network will be sending traffic simultaneously. The expected low probability that all computers 102 and servers 104 on the network will send traffic simultaneously may also be referred to as statistical burstiness of data traffic. From the network provider's point of view, the system 100 may be implemented in anticipation of: it is not possible for each computer 102 and/or server 104 to use all of the bandwidth allocated in the corresponding stream at any given time.

Instead of accurately provisioning the amount of bandwidth of a stream corresponding to the rate at which the respective network element 108 interface can process data traffic (e.g., provisioning up to a total of 1 gigabit per second streams for the network element 108 interfaces that can process up to 1 gigabit per second data traffic), system 100 may provision multiple streams having a total amount of bandwidth greater than the rate of the network element 108 interface. The amount of oversubscription provided in system 100 according to an exemplary embodiment may vary depending on the size of the flow.

Flows that are large relative to the rate of the interface of the network element 108 affect the achievable lossless oversubscription. Lossless oversubscription is a situation where no packets are lost because the network element 108 receives more traffic than can be handled. The system 100 according to an example embodiment may automatically attempt to provide lossless oversubscription when the flow through the network element 108 changes over time while maintaining high utilization of the network element 108.

In instances where the oversubscription factor on an interface of a network element 108 is statically set to the same value to cover all cases (i.e., many large flows, many small flows, a combination of large and small flows), if there are many small flows that traverse the network element 108, the oversubscription factor may be too small, resulting in low utilization of the interface of the network element 108. Conversely, if the network element 108 is expected to receive many small flows and the oversubscription factor is statically set based on this assumption, the oversubscription factor for the interface of the network element 108 is likely to be too high, which may result in latency and packet loss if there are many large flows that traverse the network element 108. For example, packet loss may occur when an interface of a network element 108 having a rate of 1 gigabit per second (Gbps) includes a 2: 1 oversubscription factor and has been provisioned with one Gbps stream over the interface. If one Gbps stream uses the entire capacity of one Gbps at any time, latency and packet loss may occur at the interface in the event that any additional streams transmit data during the same time interval. To overcome these problems of static oversubscription factors, the system 100 may dynamically adjust the oversubscription factor to improve latency and packet loss, and maintain a high level of utilization of the network elements 108.

In one exemplary embodiment, the system 100 may provision the flow based on receiving a "new flow" request. Provisioning of the new flow may use new flow processing such as, but not limited to, Call Admission Control (CAC) processing. The new flow processing may take into account the bandwidth availability on the links 112 between the network elements 108 and may also take into account the oversubscription factor for each interface of the network elements 108 to determine whether to provision the new flow.

Prior to provisioning the new flow, the computer 102 and/or server 104 may request establishment of the new flow by communicating a new flow request to an Operations Support System (OSS) 106. For example, the new flow request may be a Call Admission Control (CAC) request. The new flow request may identify the computer 102 and/or server 104 that sent the request (i.e., the requesting device) and the computer 102 and/or server 104 to which the requesting device requested communication (i.e., the target device). In an exemplary embodiment, the computer 102-1 may generate a new flow request identifying the server 104-1 to request provisioning of a flow therebetween. In another exemplary embodiment, the server 104-1 may generate a new flow request identifying the computer 102-1 to request provisioning of a flow therebetween. The following describes the requesting device as a computer 102 and the target device as a server 104. However, it is noted that the requesting device may be the server 104 and the target device may be the computer 102. After the Operation Support System (OSS)106 receives the new flow request, the system 100 may attempt to statically or dynamically provision the new flow between the requesting computer 102 and the target server 104.

In a statically provisioned network, the Operations Support System (OSS)106 may perform new flow provisioning processing, such as, but not limited to, Call Admission Control (CAC) processing for each network element 108 in the network. The Operations Support System (OSS)106 may include a provisioning module 110-4 and a traffic database 114-4. Upon receiving the new flow request, the provisioning module 110-4 may query the traffic database 114-4 to identify one or more paths on the network element 108 for the new flow between the requesting computer 102 and the target server 104. In an exemplary embodiment, the Operations Support System (OSS)106 may identify one or more paths for a new flow between the requesting computer 102 and the target server 104 using a path selection algorithm, such as, but not limited to, open shortest path first. Note that FIG. 1 illustrates a single path between computer 102 and server 104 via network elements 108-1, 108-2, and 108-3. Although system 100 may include additional network elements 108 to provide multiple paths, only a single path is shown for clarity. Moreover, it is to be appreciated that a line between devices representing links (i.e., a link between computer 102 and network element 108-1, a link between network element 108-1 and network element 108-2, etc.) includes one or more links over which different paths may be identified. For example, link 112-1 may represent three different links between network element 108-1 and network element 108-2. Each of the three different links may be considered part of a different path between network element 108-1 and network element 108-2.

Once one or more paths are identified, the provisioning module 110-4 may query the traffic database 114-4 to check for flows already provisioned on links 112 between network elements 108 on the path for each identified path. Traffic database 114-4 may include information identifying the rate of each interface of network element 108 and the bandwidth used and/or available on the interfaces of network element 108 and/or on link 112. Traffic database 114-4 may respond to queries for each interface of network element 108 for each path and/or the amount of bandwidth available at link 112. The provisioning module 110-4 may determine whether each of the network elements 108 and links 112 on at least one path has sufficient available bandwidth to support the new flow, as will be discussed in more detail below. If a path with sufficient available bandwidth is identified between the requesting computer 102 and the target server 104, the provisioning module 110-4 may provision the new flow to allow the computer 102 to communicate with the server 104 via the network elements 108 on the path. Thus, if the Operations Support System (OSS)106 statically provisions each network element 108 along the path, the system 100 does not require signaling between the network elements 108 when attempting to identify an available path, because the Operations Support System (OSS)106 may have all the bandwidth information for each network element 108 to determine whether a path is available on the network elements 108 on the path.

In dynamic provisioning, instead of the Operations Support System (OSS)106 provisioning a new flow, the Operations Support System (OSS)106 may communicate with the network element 108 to dynamically identify one or more paths for provisioning the new flow. In an exemplary embodiment, when a new flow request is received from a requesting computer 102, the Operations Support System (OSS)106 may communicate the new flow request to the endpoint network elements 108 that are closest to the requesting computer 102 and the target server 104, respectively. For example, network element 108-1 in fig. 1 may be considered the endpoint network element 108 because network element 108-1 is closest to the requesting computer 102, and network element 108-3 in fig. 1 may be considered the endpoint network element 108 because network element 108-3 is closest to the target server 104. Note, however, that endpoint network element 108 need not be the network element 108 closest to requesting computer 102 and target server 104, respectively.

Once the endpoint network element 108 is identified, the provisioning modules 110-1 and 110-3 of the endpoint network element 108 may determine whether the network elements 108-1 and 108-3, respectively, have sufficient available bandwidth to support the new flow. If network elements 108-1 and 108-3 do not have sufficient bandwidth, endpoint network element 108 may transmit a "reject new flow" message to Operation Support System (OSS)106, and Operation Support System (OSS)106 may attempt to identify other endpoint network elements 108. If no endpoint network elements are found, Operation Support System (OSS)106 may transmit a "reject new flow" message to requesting computer 102. If the endpoint network element 108 has sufficient bandwidth, the endpoint network element 108 may transmit a new flow request to other intermediate network elements 108 between the requesting computer 102 and the target server 104 in an attempt to identify one or more available paths.

When a new flow request is received at a particular intermediate network element 108 (e.g., network element 108-2), the provisioning module 110 may determine whether the particular intermediate network element 108 includes sufficient bandwidth to accommodate the new flow. The provisioning module 110 of the intermediate network element 108 may query the traffic database 114 to determine if sufficient bandwidth is available to accommodate the new flow. For example, network element 108-2 may receive a new flow request from network element 108-1 and may query traffic database 114-2 to determine whether sufficient bandwidth is available to accommodate the new flow. If the intermediate network element 108 has sufficient bandwidth, the intermediate network element 108 may transmit an acceptance message to the preceding network element 108 and may forward the new flow request to the next network element 108 in the direction of the target server 104 in an attempt to identify an available path between the requesting computer 102 and the target server 104. If the intermediate network element 108 does not have sufficient bandwidth, the intermediate network element 108 may transmit a reject new flow message to the prior network element 108, and the prior network element 108 may attempt to identify another path. If another path cannot be identified, the preceding network element 108 may transmit a deny new flow message to one or both of the endpoint network elements 108, which one or both of the endpoint network elements 108 may transmit a deny new flow message to the requesting computer 102 and/or to the Operations Support System (OSS)106 indicating that a new flow cannot be provisioned at this time.

In an exemplary embodiment, for a dynamically provisioned multiprotocol label switching (MPLS) network, network element 108 may identify a path using a routing protocol such as, but not limited to, open shortest path first-traffic engineering (OSPF-TE), and network element 108 may inform the network elements identified on the path of the total and available bandwidth on each link 112. If the oversubscription factor at the interface of one or more network elements 108 changes, and thus the total bandwidth being used by the link 112 changes, each network element 108 updates the corresponding traffic database 114 with a new bandwidth value for the link 112-1, either by internal computation on the network element 108 (i.e., dynamic provisioning) or via a provisioning command from the Operation Support System (OSS)106 (i.e., static provisioning), and may transmit the new bandwidth value to other network elements 108 and/or Operation Support Systems (OSS)106 in the network using a routing protocol. For example, the total bandwidth used on link 112-2 between network elements 108-2 and 108-3 may increase, and network element 108-2 may update traffic database 114-2 with the new bandwidth value, and network element 108-2 may transmit bandwidth update messages to network elements 108-1 and 108-3 and to Operation Support System (OSS)106 to update their respective traffic databases 114-1, 114-3, and 114-4 with the new bandwidth value for link 112-2.

As new flows are provisioned on one or more network elements 108 along the path and/or added to the MPLS tunnel through the interfaces of one or more network elements 108, one or more network elements 108 may locally update the oversubscription factor and thus may not involve signaling to other network elements 108 in the network when the bandwidth changes. For example, an MPLS Label Switched Path (LSP) of aggregated amount of bandwidth may be advertised in the network between two network elements 108, and flow call admission may be controlled into the tunnel at an endpoint network element 108 based on the tunnel oversubscription factor and the tunnel bandwidth. Also, if the current tunnel does not have sufficient bandwidth to support the new flow, network element 108 may automatically attempt to signal to establish a larger tunnel, which may or may not involve a change in the oversubscription factor for one or more interfaces of network element 108.

The following describes calculations for determining whether a new flow may be provisioned, according to an example embodiment. Instead of configuring a single fixed oversubscription factor for the interface of the network element 108 having rate 'L', the network element 108 according to an example embodiment may have a dynamic oversubscription factor 'n'. The oversubscription factor may be the amount of bandwidth provisioned on an interface of the network element 108 divided by the maximum amount of bandwidth that the interface of the network element 108 can handle (i.e., the rate L of the interface). The dynamic oversubscription factor may be based on the following formula:

oversubscription factor formula:wherein

LF₀、LF₁、...、LF_nIs the set of all flows having a flow rate greater than or equal to rate 'a', where n is 0, 1, 2, 3₀、SF₁、...、SF_mIs the set of all streams having a stream rate less than rate a, where m is 0, 1, 2, 3. In an example embodiment, the rate a may be a percentage of the maximum rate of the interface of the network element 108. For example, network element 108 may operate at a maximum rate of 1,000 megabits per second (Mbps), and rate a may be 50% of the maximum rate (i.e., 500 Mbps). Thus, a stream at 500Mbps or higher may be considered large, and a stream at a rate less than 500Mbps may be considered small. Also, rate a may be set to the rate of the largest flow provisioned on network element 108 and the rate of the second largest flow provisioned on network element 108, etc.

In one exemplary embodiment, the large flow LF may have a large flow oversubscription factor 'x' and the small flow SF may have a small flow oversubscription factor 'z' for the small flows. For example, an experienced business engineer may select large and small flow oversubscription factors. The system 100 may also automatically adjust the large and small flow oversubscription factors based on network traffic conditions such as, but not limited to, the number and size of provisioned data flows. The new flow may be provisioned on the interface of the network element 108 as long as the calculated dynamic oversubscription factor n satisfies the following constraint:

the restriction formula:

therefore, whenWhen it is, then

In that case, thenWhich is a large flow over subscription factor.

And whenWhen it is, then

In that case, thenWhich is a small-flow over-subscription factor. If it is assumed that the large oversubscription factor x is less than the small oversubscription factor z, then x ≦ n ≦ z.

Prior to determining whether to provision the new flow, an Operations Support System (OSS)106 in static provisioning and/or a network element 108 in dynamic provisioning may determine whether adding the new flow to an existing flow would violate a restriction formula.

If adding a new flow would violate the restriction formula, the oversubscription factor for the interface of each network element 108 may not be changed, and the Operations Support System (OSS)106 and/or the network element 108 may send a reject new flow message indicating that the new flow cannot be added, and/or may send a reject new flow message indicating that a previous network element 108 attempted to identify an alternate path through a different network element 108. If adding the new flow would not violate the restriction formula, the Operations Support System (OSS)106 and/or the network element 108 may calculate a new dynamic oversubscription factor 'n' using the oversubscription factor formula for the interface of the network element 108, may update the corresponding traffic database 114, and may transmit an acceptance message on the path to the Operations Support System (OSS)106 and/or the other network element 108. Once all oversubscription factors have been updated at each network element 108 interface, the Operations Support System (OSS)106 and/or the network elements 108 may allocate bandwidth to provision the new flow and may transmit a provisioned message to notify the requesting computer 102 that the flow has been provisioned, thereby allowing the computer 102 and the server 104 to transmit data via the provisioned flow. Thus, the system 100 can efficiently provision new flows to improve utilization and minimize packet delay and/or loss.

Fig. 2 illustrates a method for performing new flow provisioning according to an example embodiment. This exemplary method is provided as an example, as there are various ways to perform the methods disclosed herein. The method 200 shown in fig. 2 may be performed or otherwise implemented by one or a combination of various systems. The method 200 is described below as being performed by the system 100 shown in fig. 1, for example, and various elements of the system 100 are referenced in explaining the example method of fig. 2. Each block shown in fig. 2 represents one or more processes, methods, or subroutines performed in exemplary method 200. Referring to fig. 2, exemplary method 200 may begin at block 202.

In block 202, the method 200 may include receiving a new flow request requesting provisioning of a new flow between a computer and a server. In an example embodiment, the computer 102 and/or server 104 may transmit a new flow request (e.g., a Call Admission Control (CAC) request) to the Operations Support System (OSS) 106. The method 200 may continue to block 204.

In block 204, the method 200 may include: a path between the computer 102 and the server 104 is identified. In an exemplary embodiment, the Operations Support System (OSS)106 may identify one or more paths between the computer 102 and the server 104. Moreover, in a dynamically provisioned network, the Operations Support System (OSS)106 may provision the endpoint network elements 108 on the network, and the endpoint network elements 108 may then notify available bandwidth end-to-end on the intermediate network elements 108 between the computer 102 and the server 104 to identify one or more paths, as opposed to the Operations Support System (OSS)106 identifying one or more paths. In one exemplary embodiment, other network elements 108 in the network may be notified of the available bandwidth on each of the MPLS interfaces of the network element 108 via OSPF-TE so that each network element 108 in the network has an entry in its traffic engineering database 114 for all MPLS interfaces. The Operations Support System (OSS)106 may determine whether sufficient bandwidth is available for the new flow on the network elements 108-1 and 108-3. If sufficient bandwidth is available, network elements 108-1 and 108-3 may notify intermediate network element 108-2 of the bandwidth, which may perform a new flow provisioning process at intermediate network element 108-2. The method 200 may continue to block 206.

In block 206, the method 200 may include: it is determined whether provisioning a new flow will violate the restriction. In an exemplary embodiment, for statically provisioned paths, the Operations Support System (OSS)106 may determine whether adding a new flow would violate a restriction formula for any network elements 108 on the identified path. In a dynamically provisioned network, one or more network elements 108 on the identified path may individually determine whether adding a new flow would violate the restriction formula. The method 200 may continue to block 208.

In block 208, the method 200 may include determining whether the limit is satisfied. In an exemplary embodiment, for a statically provisioned path, the Operations Support System (OSS)106 may determine whether the restrictions are satisfied on all network elements 108 on the identified path. In a dynamically provisioned network, one or more of the network elements 108 may determine whether the restrictions are satisfied on all of the network elements 108 on the identified path. If the limits are satisfied, the method 200 may continue to block 210. If the limits are not met, the method 200 may continue to block 214.

In block 210, the method 200 may include updating the oversubscription factor. In an exemplary embodiment, for statically provisioned paths, the Operations Support System (OSS)106 may calculate and update the traffic database 114 of each network element 108 to include the new oversubscription factor. In a dynamically provisioned network, one or more network elements 108 may calculate and update the traffic database 114 of each network element 108 to include the new oversubscription factor n, and/or the network elements 108 may individually calculate and update the traffic database 114 to include the new oversubscription factor. The method 200 may continue to block 212.

In block 212, the method 200 may include provisioning the new stream through a path between the computer and the server. In an exemplary embodiment, the Operations Support System (OSS)106 may allocate bandwidth to provision the new flow and may transmit the provisioned message to the computer 102, thereby notifying the computer 102 that the new flow has been provisioned and is available for communication with the server 104. This branch of method 200 may then end. Returning to block 208, if the limits are not met, the method 200 may continue to block 214.

In block 214, the method 200 may include determining whether an alternate path exists between the computer 102 and the server 104. In an exemplary embodiment, the Operations Support System (OSS)106 and/or one or more network elements 108 may check whether another path exists between the computer 102 and the server 104. For example, the Operations Support System (OSS)106 and/or one or more network elements 108 may use a routing protocol to determine whether an appropriate alternate path exists. If an alternate path exists, the method 200 may return to block 206. If an alternate path does not exist, the method 200 may continue to block 216.

In block 216, the method 200 may include generating a reject new flow message. In an exemplary embodiment, one of the Operations Support System (OSS)106 and/or the network element 108 may transmit a reject new flow message to the computer 102 and/or the server 104 that generated the new flow request indicating that the new flow cannot be provisioned at this time. This branch of method 200 may then end.

Fig. 3 illustrates a method for deleting provisioned flows in accordance with an example embodiment. This exemplary method is provided as an example, as there are various ways to perform the methods disclosed herein. The method 300 shown in fig. 3 may be performed by or otherwise implemented by one or a combination of various systems. The method 300 is described below as being performed, for example, by the system 100 shown in FIG. 1, and various elements of the system 100 are referenced in explaining the exemplary method of FIG. 3. Each block shown in fig. 3 represents one or more processes, methods, or subroutines performed in exemplary method 300. Referring to fig. 3, exemplary method 300 may begin at block 302.

In block 302, the method 300 may include receiving a delete stream request. In an example embodiment, Operations Support System (OSS)106 and/or one or more network elements 108 may receive a delete stream request from computer 102 and/or server 104. The Operations Support System (OSS)106 and one or more network elements 108 may transmit a delete flow request to all other network elements 108 on the path associated with the flow. The method 300 may continue to block 304.

In block 304, the method 300 may include deleting the identified stream associated with the delete stream request. According to an example embodiment, network element 108 may delete the flow associated with the delete flow request, thereby freeing up resources of network element 108. The method 300 may continue to block 306.

In block 306, the method 300 may include determining whether any streams remain. In an example embodiment, the Operations Support System (OSS)106 and/or each network element 108 may determine whether the network element 108 has any other provisioned flows. If additional streams remain, the method 300 may continue to block 308. If no streams remain, the method 300 may continue to block 310.

In block 308, the method 300 may include updating the oversubscription factor. In an exemplary embodiment, the Operations Support System (OSS)106 and/or each network element 108 may update the oversubscription factor n based on the remaining flows. This branch of method 300 may then end. Returning to block 306, the method 300 may continue to block 310 without any other streams remaining.

In block 310, the method 300 may include resetting the oversubscription factor. In an exemplary embodiment, the Operations Support System (OSS)106 may transmit a reset message to the network elements 108 to reset the oversubscription factor stored in the respective traffic database 114 when no other flows are provisioned on the interfaces of those network elements 108. Moreover, the provisioning module 110 of a network element 108 that does not have a provisioned flow on the interface may individually reset the oversubscription factor in the corresponding traffic database 114. This branch of method 300 may then end.

Various examples are provided below for determining whether adding a new flow would violate a restriction and calculating an oversubscription factor, according to exemplary embodiments. As described above, variable L may represent the rate of a particular interface of network element 108, variable x may represent a large oversubscription factor, variable z may represent a small oversubscription factor, and variable n may represent an oversubscription factor calculated based on adding a new flow to a previously provisioned flow.

Example 1

In example 1, the interface rate L is 1000Mbps, the large flow oversubscription factor x is 1, the small flow oversubscription factor z is 2, and all flows except the maximum flow are treated as small flows. In this example, a single maximum stream is not oversubscribed, and all remaining streams are oversubscribed in a 2: 1 ratio. If the maximum stream is 500Mbps, the sum of the maximum streams is 500 Mbps. The limiting formula can then be solved to determine the maximum allowable value for the sum of the minimum flows SF. Applying the restriction formula yields:

for theThe solution provides:

therefore, the sum of all streamlet rates may be less than 1000Mbps to satisfy the constraint equation. Thus, the maximum oversubscription factor for an interface of a network element is:

if for example the sum of the streamlets SF is 400Mbps, another 600Mbps of bandwidth may be allocated to the other streamlets (i.e. 1000-400 Mbps-600 Mbps).

Example 2

Continuing with example 1, if a new stream request is received requesting to add an additional 600Mbps stream, the new stream cannot be provisioned because adding the 600Mbps stream will not satisfy the restriction formula becauseWill be greater than L. In this example, the rate a for defining the boundary between the large flow and the small flow is the flow having the maximum flow rate. Therefore, the temperature of the molten metal is controlled,will go from 500Mbps to 600Mbps, and 500Mbps will be treated as a streamlet. Then:

consider the constraint equation:

the result is greater than the 1000Mbps rate of the interface of network element 108, so the new flow request to add 600Mbps violates the restriction formula. Therefore, the new flow request will be denied.

Determining whether to provision a new flow may be applied to a link aggregation environment based on an analysis restriction formula, such as, but not limited to, IEEE standard 802.3-2005 clause 43 link aggregation standard, the contents of which are incorporated herein by reference in their entirety. Other link aggregation standards may be used in place of or in addition to the IEEE Standard 802.3-2005 clause 43 link aggregation standard. Link aggregation allows the use of multiple parallel links to increase the amount of data transferred between two devices beyond what can be transferred using a single link.

Fig. 4 illustrates a link aggregation environment with multiple links between network elements, according to an example embodiment. Links 112-3, 112-4, and 112-5 are depicted between network element 108-4 and network element 108-5. Note that fig. 4 illustrates three links 112 between network element 108-4 and network element 108-5. However, link aggregation may be implemented using one or more links located between two devices (e.g., between a network element and a server, between a first network element and a second network element, etc.).

The system 100 according to example embodiments may improve flow provisioning in a link aggregation environment. Conventionally, a link aggregation environment such as IEEE Standard 802.3-2005 clause 43 link aggregation randomly provisions the link 112 with flows. For example, the Operations Support System (OSS)106 and/or the network element 108 may randomly assign a new flow to one of the links 112-3, 112-4, and 112-5. If several small flows are randomly distributed over the link 112, it is possible for the flows to be evenly assigned to different links 112.

A problem may occur in a link aggregation environment when the bandwidth of a flow increases and approaches a certain percentage (e.g., greater than 50%) of the rate of the interface of the network element 108. For example, if each link 112 has a rate of 1 gigabit per second (Gbps) and is equipped with three separate 1 gigabit per second streams, if the streams are randomly assigned to links 112-3, 112-4, and 112-5, it is possible that two of the three separate 1 gigabit per second streams may be equipped to the same link (e.g., two separate 1 gigabit per second streams to link 112-4) and none of the three separate 1 gigabit per second streams is equipped to one of the links. This may result in one of the three links 112 not being utilized and one of the three links 112 being over-utilized, resulting in latency and/or packet loss.

To overcome the problems associated with randomly assigning flows to links, system 100 may utilize a restriction formula as described above to intelligently determine whether to assign a new flow to each link 112-3, 112-4, and 112-5 between network element 108-4 and network element 108-5. For example, as described above, whenThenWhich is a large flow over subscription factor. Thus, if x is 1 and one of the three links 112 from fig. 4 having a 1 gigabit per second rate can be provided with three independent 1 gigabit per second streams, the restriction formula will prevent more than one of the three independent 1 gigabit per second streams from being provided on one of the three 1 gigabit per second rate links 112. Thus, provisioning flows using a restriction formula may improve utilization of links 112 in a link aggregation environment and may reduce the potential for latency and/or data loss.

In the foregoing specification, various preferred embodiments have been described with reference to the accompanying drawings. It will, however, be evident that various modifications and changes may be made thereto, and additional embodiments may be implemented, without departing from the broader scope of the invention as set forth in the appended claims. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.

Claims

1. A method for providing efficient provisioning of data streams, comprising:

receiving a new flow request for requesting provisioning of a flow between a computer and a server;

identifying a path of one or more network elements between the computer and the server, each of the one or more network elements including an interface;

determining whether provisioning the flow between the computer and the server violates a restriction, wherein the restriction is based on at least one of:

a large flow oversubscription factor, wherein a large flow is a flow that is greater than a specified percentage of the maximum interface rate of an interface, and

a small flow oversubscription factor, wherein a small flow is a flow that is less than a specified percentage of the maximum interface rate of the interface;

updating an oversubscription factor and an available bandwidth for an interface of each of the one or more network elements in the path based at least in part on the new flow request without violating the limit, and

determining whether a second path exists between the computer and the server in the event that the constraint is violated,

wherein the oversubscription factor isLF₀、LF₁、…、LF_nIs the set of all large flows, where n is 0, 1, 2, 3, … n, and SF₀、SF₁、…、SF_mIs a set of all streamlets, where m is 0, 1, 2, 3, … p, and L is an interface rate of at least one of the interfaces;

wherein the limitation isx is the large oversubscription factor and z is the small oversubscription factor.

2. The method of claim 1, wherein the limiting is based on an interface rate of at least one of the interfaces.

3. The method of claim 2, wherein the limit is associated with a sum of all large flows divided by a large flow oversubscription factor and a sum of all small flows divided by a small flow oversubscription factor being less than or equal to the interface rate.

4. The method of claim 2, wherein the interface rate is a rate of a maximum flow on at least one of the one or more network elements.

5. The method of claim 3, wherein the large oversubscription factor is less than the small oversubscription factor.

6. The method of claim 1, wherein the oversubscription factor is based on a sum of all flows on at least one of the interfaces of the one or more network elements and on an interface rate of the at least one of the interfaces.

7. The method of claim 1, wherein the limiting is based on a large flow over subscription factor.

8. The method of claim 1, wherein the limiting is based on a small flow over subscription factor.

9. The method of claim 1, wherein the oversubscription factor changes based on a number of large flows and a number of small flows on at least one of the interfaces of the one or more network elements.

10. The method of claim 1, wherein the determination of whether provisioning the flows between the computer and the server would violate a restriction is used to determine whether a sum of flows provisioned on at least one of the interfaces of the one or more network elements is greater than or equal to an interface rate of the at least one of the interfaces.

11. The method of claim 1, wherein the reject new flow message is transmitted in the absence of the second path.

12. The method of claim 1, wherein the path is identified using a routing protocol.

13. The method of claim 1, wherein the path is identified using a traffic engineering database.

14. A method for providing efficient provisioning of data streams, comprising:

receiving, at a first network element, a new flow request from a second network element, the new flow request being usable to request provisioning of a new flow on an interface of the first network element;

determining whether provisioning the new flow violates a restriction, wherein the restriction is based on at least one of:

updating an oversubscription factor and bandwidth of the interface based at least in part on the new flow request, transmitting an acceptance message to the second network element and transmitting the new flow request to a third network element without violating the limit, and

transmitting a reject new flow message to the second network element in case of violation of the restriction,

wherein the oversubscription factor isLF_０、LF_１、…、ＬＦ_nIs the set of all large flows, where n is 0, 1, 2, 3, … n, and SF₀、SF_１、…、SF_mIs a set of all streamlets, where m is 0, 1, 2, 3, … p, and L is an interface rate of at least one of the interfaces;

wherein the limitation is

x is the large oversubscription factor and z is the small oversubscription factor.

15. The method of claim 14, wherein the first network element updates bandwidth information in a traffic database if the limit is not violated.

16. A system for providing efficient provisioning of data streams, comprising:

means for receiving a new streaming request requesting provisioning of a stream between a computer and a server,

means for identifying a path of one or more network elements between the computer and the server, each of the one or more network elements comprising an interface;

means for determining whether provisioning the flow between the computer and the server violates a restriction, wherein the restriction is based on at least one of:

means for updating an oversubscription factor and available bandwidth for an interface of each of the one or more network elements in the path based at least in part on the new flow request without violating the limit, and

means for determining whether a second path exists between the computer and the server in the event that the constraint is violated,

wherein the oversubscription factor isLF₀、LF_１、…、LF_mIs the set of all large flows, where n is 0, 1, 2, 3, … n, and SF₀、SF_１、…、SF_mIs a set of all streamlets, where m is 0, 1, 2, 3, … p, and L is an interface rate of at least one of the interfaces;

wherein the limitation is