Dual scheduling for efficient network traffic management

Abstract

Data traffic is scheduled by, in a first scheduler, selecting a source of traffic from a plurality of sources of traffic, each source being associated with a second scheduler, in a second scheduler associated with the selected source of traffic, selecting a type of traffic from a plurality of types of traffic within the source selected by the first scheduler, and transmitting data of the selected type and source.

1 . A method of scheduling data traffic comprising 
 (a) in a first scheduler, selecting a source of traffic from a plurality of sources of traffic, each source being associated with a second scheduler,    (b) in a second scheduler associated with the selected source of traffic, selecting a type of traffic from a plurality of types of traffic within the source selected by the first scheduler, and    (c) transmitting data of the selected type and source.    
     
     
         2 . The method of  claim 1  also comprising repeating steps (a)-(c).  
     
     
         3 . The method of  claim 1  in which the traffic is traffic for passing over a communications link.  
     
     
         4 . The method of  claim 3  in which the selecting comprises scheduling the selection of sources and types according to characteristics of the communications link.  
     
     
         5 . The method of  claim 1  in which selecting a source of traffic comprises selecting a source from which packets should be delivered according to a rule.  
     
     
         6 . The method of  claim 5  in which delivering packets according to the rule comprises one or more of 
 guaranteeing a minimum bandwidth for a source of the plurality of sources,    guaranteeing a maximum burst limit for a source of the plurality of sources, and    guaranteeing a service interval to a source of the plurality of sources.    
     
     
         7 . The method of  claim 1  in which choosing a source of traffic comprises allowing a user to configure a preemptive priority for a type of traffic.  
     
     
         8 . The method of  claim 1  also comprising in the first scheduler, accounting for bandwidth used by each source of traffic.  
     
     
         9 . The method of  claim 1  in which selecting a type of traffic comprises 
 selecting a type from which packets should be delivered according to a rule.    
     
     
         10 . The method of  claim 9  in which delivering packets according to the rule comprises one or more of 
 guaranteeing a minimum bandwidth to a type, within an amount of bandwidth allocated by the first scheduler,    guaranteeing a maximum burst limit to a type, within a burst limit allocated by the first scheduler, and    guaranteeing a service interval to a type.    
     
     
         11 . The method of  claim 1  in which the types of traffic comprise overlapping classifications of traffic.  
     
     
         12 . The method of  claim 1  also comprising, before the selecting, filtering the traffic based on routes the traffic will use.  
     
     
         13 . The method of  claim 12  in which the filtering comprises applying a radix tree algorithm.  
     
     
         14 . The method of  claim 1  also comprising 
 determining that a packet from the selected type is to be transmitted through a tunnel, and    in which selecting a type includes charging the type for bandwidth usage based on an average efficiency of the tunnel.    
     
     
         15 . A method of scheduling data traffic comprising 
 selecting a type of traffic, and    determining that a packet from the selected type is to be transmitted through a tunnel,    in which selecting the type includes charging the type for bandwidth usage based on an average efficiency of the tunnel.    
     
     
         16 . The method of  claim 15  also comprising adding the selected packet to a queue for the tunnel.  
     
     
         17 . The method of  claim 16  also comprising extracting a packet from the queue for the tunnel based on one or more of 
 efficiency of the tunnel,    responsiveness of the tunnel,    a maximum delay of the tunnel, and    a minimum buffer of the tunnel.    
     
     
         18 . The method of  claim 15  also comprising 
 compressing packets in the queue for the tunnel,    updating an average compression ratio of the tunnel, and    transmitting the compressed packets according to a scheduler that selects sources of traffic from a plurality of sources of traffic.    
     
     
         19 . The method of  claim 15  also comprising 
 encrypting packets in the queue for the tunnel,    updating an average expansion ratio of the encryption, and    transmitting the encrypted packets according to a scheduler that selects sources of traffic from a plurality of sources of traffic.    
     
     
         20 . The method of  claim 1  in which selecting a type comprises 
 using a class-based queuing algorithm.    
     
     
         21 . A method of scheduling data traffic comprising 
 selecting a source of traffic from a plurality of sources of traffic using a group ratio round robin scheduling algorithm.    
     
     
         22 . The method of  claim 21  in which using a group ratio round robin scheduling algorithm comprises 
 defining an ordered set of groups of sources of traffic having similar weights,    computing ratios between total weights of the groups,    repeatedly, 
 choosing one of the groups,  
 within the chosen group, using a second algorithm to choose a source of traffic,  
 transmitting an amount of traffic from the chosen source.  
   
     
     
         23 . The method of  claim 22  in which the second algorithm is a deficit round robin scheduling algorithm.  
     
     
         24 . The method of  claim 22  also comprising 
 computing a deficit credit and quantum credit for each group based on the ratios, and    after the transmitting, updating a deficit counter and a quantum counter for the chosen group based on the amount of traffic transmitted and the credits.    
     
     
         25 . The method of  claim 22  in which choosing one of the groups comprises 
 if the deficit counter and the quantum counter of the last-chosen group are above zero, choosing the last-chosen group,    if the deficit counter of the last-chosen group is at or below zero, adding the deficit credit to the deficit counter, adding a quantum credit to the quantum counter, and choosing the next group of the ordered set of groups, and    if the deficit counter of the last-chosen group is above zero and the quantum counter is at or below zero, adding a quantum credit to the quantum counter for that group, and choosing the first group in the ordered set of groups.    
     
     
         26 . A computer-readable medium comprising instructions to repeatedly cause 
 a first scheduler to select a source of traffic from a plurality of sources of traffic, each source being associated with a second scheduler,    a second scheduler associated with the selected source of traffic to select a type of traffic from a plurality of types of traffic within traffic from the source selected by the first scheduler, and    data of the selected type and source to be transmitted.    
     
     
         27 . A device for scheduling data traffic comprising 
 a first scheduler configured to select a source of traffic from a plurality of sources of traffic, each source being associated with a second scheduler, and    a second scheduler, associated with the selected source of traffic, configured to select a type of traffic from a plurality of types of traffic within traffic from the source selected by the first scheduler.    
     
     
         28 . A method comprising 
 determining an amount of bandwidth to be used by a compression tunnel,    determining a pre-compression bandwidth limit for a type of traffic,    determining a post-compression bandwidth limit for the tunnel,    compressing data, including data from the type,    determining a compression ratio,    based on the compression ratio, 
 determining an amount of pre-compression bandwidth used by the tunnel, and  
 determining an amount of post-compression bandwidth used by the tunnel, and  
   communicating the determined amounts to a scheduling process for the type.    
     
     
         29 . The method of  claim 28  also comprising 
 for each of a plurality of types of traffic, guaranteeing an amount of bandwidth, determination of the guaranteed amount being based on the compression ratio.    
     
     
         30 . The method of  claim 28  also comprising scheduling types to use the tunnel based on the compression ratio and the determined amounts.  
     
     
         31 . A computer-readable medium comprising instructions to cause a device to 
 determine an amount of bandwidth to be used by a compression tunnel,    determine a pre-compression bandwidth limit for a type of traffic,    determine a post-compression bandwidth limit for the tunnel,    compress data, including data from the type,    determining a compression ratio,    based on the compression ratio, 
 determine an amount of pre-compression bandwidth used by the tunnel, and  
 determine an amount of post-compression bandwidth used by the tunnel, and communicate the determined amounts to a scheduling process for the type.  
   
     
     
         32 . A device for scheduling data traffic configured to 
 determine an amount of bandwidth to be used by a compression tunnel,    determine a pre-compression bandwidth limit for a type of traffic,    determine a post-compression bandwidth limit for the tunnel,    compress data, including data from the type,    determining a compression ratio,    based on the compression ratio, 
 determine an amount of pre-compression bandwidth used by the tunnel, and  
 determine an amount of post-compression bandwidth used by the tunnel, and communicate the determined amounts to a scheduling process for the type.  
   
     
     
         33 . A method comprising 
 for a plurality of endpoints of routes through a network, identifying pairs of endpoints that can support tunnels to each other,    recording in a definition file identifications of the identified pairs of endpoints, and    at each endpoint, 
 receiving the definition file,  
 reading from the definition file the identifications of other endpoints that the endpoint is paired with, and  
 creating a tunnel to each paired endpoint.  
   
     
     
         34 . The method of  claim 33  in which the identifying and recording is performed by a centralized server.  
     
     
         35 . A computer-readable medium comprising instructions to cause a device to 
 for a plurality of endpoints of routes through a network, identify pairs of endpoints that can support tunnels to each other,    record in a definition file identifications of the identified pairs of endpoints, and    at each endpoint, 
 receive the definition file,  
 read from the definition file the identifications of other endpoints that the endpoint is paired with, and  
 create a tunnel to each paired endpoint.  
   
     
     
         36 . A device configured to 
 for a plurality of endpoints of routes through a network, identify pairs of endpoints that can support tunnels to each other,    record in a definition file identifications of the identified pairs of endpoints, and    at each endpoint, 
 receive the definition file,  
 read from the definition file the identifications of other endpoints that the endpoint is paired with, and  
 create a tunnel to each paired endpoint.  
   
     
     
         37 . A method comprising 
 receiving data packets to be transmitted,    for each packet, 
 identifying a class and a link,  
 determining whether the packet should be transmitted using a tunnel, and  
 adding the packet to a queue of packets having the same class as the packet, selecting a class of packets,  
   adding packets from the selected class which are to be transmitted using the tunnel to a queue for the tunnel,    adapting the packets in the queue for the tunnel, producing adapted packets    adding adapted packets to a queue of packets to be transmitted on the link identified for the packets,    selecting a link, and    transmitting packets from the queue for that link.    
     
     
         38 . The method of  claim 37  in which adapting the packets comprises compressing the packets.  
     
     
         39 . The method of  claim 37  in which adapting the packets comprises encrypting the packets.  
     
     
         40 . The method of  claim 37  in which adapting the packets comprises encrypting and compressing the packets.  
     
     
         41 . The method of  claim 37  in which selecting a class of packets comprises 
 determining, for each class of packets, 
 a number of bytes that have been compressed,  
 a number of compressed bytes that have been transmitted, and  
 a compression ratio, and  
   selecting a class based on the compression ratio and the number of compressed bytes that have been transmitted for each class.    
     
     
         42 . The method of  claim 37  in which adapting the packets for the tunnel comprises, for each packet, 
 removing a network header from the packet,    performing an operation on the packet to create an adapted packet, and    adding a network header corresponding to a destination to the adapted packet,    the method also comprising 
 receiving transmitted packets at the destination, and  
 for each packet that was transmitted using the tunnel, 
 performing an inverse of the operation on the packet,  
 adding a second network header to the packet, and  
 transmitting the packet according to the second network header.  
 
   
     
     
         43 . A computer-readable medium comprising instructions to cause a device to 
 receive data packets to be transmitted,    for each packet, 
 identify a class and a link,  
 determine whether the packet should be transmitted using a tunnel, and  
 add the packet to a queue of packets having the same class as the packet, select a class of packets,  
   add packets from the selected class which are to be transmitted using the tunnel to a queue for the tunnel,    adapt the packets in the queue for the tunnel, producing adapted packets    add adapted packets to a queue of packets to be transmitted on the link identified for the packets,    select a link, and    transmit packets from the queue for that link.    
     
     
         44 . A device configured to 
 receive data packets to be transmitted,    for each packet, 
 identify a class and a link,  
 determine whether the packet should be transmitted using a tunnel, and  
 add the packet to a queue of packets having the same class as the packet, select a class of packets,  
   add packets from the selected class which are to be transmitted using the tunnel to a queue for the tunnel,    adapt the packets in the queue for the tunnel, producing adapted packets    add adapted packets to a queue of packets to be transmitted on the link identified for the packets,    select a link, and    transmit packets from the queue for that link.