SWAN: achieving high utilization in networks

Abstract

Greater network utilization is implemented through dynamic network reconfiguration and allocation of network services and resources based on the data to be transferred and the consumer transferring it. A hierarchical system is utilized whereby requests from lower layers are aggregated before being provided to upper layers, and allocations received from upper layers are distributed to lower layers. To maximize network utilization, paths through the network are reconfigured by identifying specific types of packets that are to be flagged in a specific manner, and then by further identifying specific routing rules to be applied in the transmission of such packets. Network reconfiguration is performed on an incremental basis to avoid overloading a path, and capacity can be reserved along one or more paths to prevent such overloading. Background data is agnostic as to specific transmission times and is utilized to prevent overloading due to reconfiguration.

We claim: 
     
       1. A system comprising:
 a controller performing steps comprising:
 receiving aggregated requests for network service 
 receiving network information about a network providing the network service; 
 allocating the network service into aggregate service allocations in accordance with the received network information; and 
 responding to the aggregated requests with the aggregate service allocations; and 
 
 at least one service broker performing steps comprising:
 receiving individual requests for the network service; 
 aggregating the received individual requests into at least one of the aggregated requests for the network service; 
 transmitting the at least one of the aggregated requests to the controller; 
 receiving, in response to the transmitted at least one of the aggregated requests, at least one of the aggregate service allocations; and 
 doling out allocations of the network service, from the received at least one of the aggregate service allocations, in response to the received individual requests for the network service. 
 
 
     
     
       2. The system of  claim 1 , further comprising a network controller, different from the controller, the network controller performing steps comprising:
 receiving from the network, the network information; 
 receiving, from the controller, packet labeling and forwarding rules for implementing the aggregate service allocations; 
 wherein the packet labeling rules identify packets to be labeled with a first identifier and wherein further the forwarding rules identify one or more links of the network through which to transmit a packet labeled with the first identifier. 
 
     
     
       3. The system of  claim 1 , wherein the controller performs further steps comprising: estimating a utilization of the network service by interactive data, the interactive data bypassing the controller's service allocations. 
     
     
       4. The system of  claim 1 , wherein the allocation of the network service is performed by the controller in accordance with precomputed paths through the network, each link of each precomputed path having a capacity informing the allocation of the network service. 
     
     
       5. The system of  claim 1 , wherein the controller performs further steps comprising: establishing a callback mechanism with one or more of the at least one service broker; and utilizing the established callback mechanism to modify at least a portion of a previously provided service allocation due to a topology change in the network. 
     
     
       6. The system of  claim 1 , wherein the at least one broker performs further steps comprising: doling out, in response to a newly received individual request for the network service, allocations of the network service from an excess allocated to the at least one broker prior to receiving the newly received individual request. 
     
     
       7. The system of  claim 1 , wherein the controller performs further steps comprising: reconfiguring the network from a first configuration to a second configuration by temporarily and incrementally changing a network configuration so as to avoid overcapacity on any one or more links of the network as part of the reconfiguration to the second configuration. 
     
     
       8. The system of  claim 7 , wherein the temporary and incremental changes to the network configuration result in at least one link receiving an increased utilization during the temporary and incremental change, the increased utilization consuming either excess capacity of the link or capacity of the link freed up by the stopping of utilization of the link capacity by background data transfers. 
     
     
       9. The system of  claim 1 , wherein the individual requests for the network service comprise an indication of a temporal requirement of such requests and a priority of such request. 
     
     
       10. The system of  claim 1 , wherein the allocations of the network service doled out by the at least one service broker are enforced by consumers of the network service to whom the allocations of the network service were doled out. 
     
     
       11. A method of allocating a network service, the method comprising the steps of:
 receiving requests for the network service, the requests comprising requests to transfer elastic data in a time-specified manner and requests to transfer background data in an opportunistic manner; 
 receiving information about the network providing the network service; 
 estimating a utilization of the network service by interactive data bypassing the allocations; and 
 generating packet labeling and packet forwarding rules, the packet labeling rules identifying at least one collection of packets to be labeled with a first label and the packet forwarding rules specifying at least one link through which to transmit packets labeled with the first label, the generated packet labeling and packet forwarding rules allocating a remaining network service first to the elastic data transfer requests and then to the background data transfer requests. 
 
     
     
       12. The method of  claim 11 , wherein a determination of the remaining network service is made in view of precomputed paths through the network, each link of each precomputed path having a capacity informing the determination of the remaining network service. 
     
     
       13. The method of  claim 11 , further comprising the steps of:
 reconfiguring the network from a first configuration to a second configuration by temporarily and incrementally changing a network configuration so as to avoid overcapacity on any one or more links of the network as part of the reconfiguration to the second configuration. 
 
     
     
       14. The method of  claim 13 , wherein the temporary and incremental changes to the network configuration result in at least one link receiving an increased utilization during the temporary and incremental change, the increased utilization consuming either excess capacity of the link or capacity of the link freed up by the stopping of utilization of the link capacity by background data transfers. 
     
     
       15. The method of  claim 11 , further comprising the steps of:
 generating an aggregate network service allocation comprised of an aggregation of network service allocations for multiple consumers of the network service; and 
 transmitting the aggregate service allocation to a service broker in response to an aggregated request for the network service from the service broker. 
 
     
     
       16. The method of  claim 15 , further comprising the steps of: establishing a callback mechanism with the service broker; and utilizing the established callback mechanism to modify at least a portion of a network service allocation previously provided to the service broker. 
     
     
       17. A method of reconfiguring a network, the method comprising the steps of:
 selecting a second configuration into which to reconfigure a network currently in a first configuration differing from the second configuration; 
 selecting a next incremental configuration, differing from both the first configuration, the second configuration and a preceding incremental configuration, the next incremental configuration differing from the preceding incremental configuration and thereby causing at least one link to receive an increased utilization, the increased utilization consuming either excess capacity of the link or capacity of the link freed up by the stopping of utilization of the link capacity by background data transfers; and 
 repeating the selecting the next incremental configuration until the network is configured in the second configuration. 
 
     
     
       18. The method of  claim 17 , further comprising the steps of: generating packet labeling and packet forwarding rules, the packet labeling rules identifying at least one collection of packets to be labeled with a first label and the packet forwarding rules specifying at least one link through which to transmit packets labeled with the first label, the generated packet labeling and packet forwarding rules resulting in a change from the preceding incremental configuration to the next incremental configuration. 
     
     
       19. The method of  claim 17 , wherein the second configuration provides greater network service to allocate than the first configuration. 
     
     
       20. The method of  claim 12 , wherein the selecting the next incremental configuration is made in view of precomputed paths through the network, each link of each precomputed path having a capacity informing the selecting the next incremental configuration.