Method and apparatus for load-sensitive routing of long-lived packet flows

Abstract

The present invention builds on the implications of variability in flow durations on the stability of load-sensitive routing. In accordance with an embodiment of the present invention, long-lived flows of packets are routed dynamically while short-lived flows are forwarded on preprovisioned static paths. This hybrid approach can exploit flow-classification hardware at the edge of backbone networks and known techniques for flow-pinning, as well as basic insights from earlier work on QoS routing. This approach of separating short-lived and long-lived flows can dramatically improve the stability of dynamic routing.

1. A method of routing packets in a packet-switched network comprising the steps of:
 establishing a static route for packets in the packet-switched network;  
 classifying a first group of packets as a long-lived flow; and  
 establishing a load-sensitive route for the long-lived flow, and 
 whereininitially routing flows of long-lived packets are initially routed  over the static route and continue to be routed  continuing to route the flows of long- lived packets  over the static route if a load-sensitive route with adequate capacity cannot be established,  
   wherein the establishing a load - sensitive route includes using a dynamic routing algorithm to identify the load - sensitive route,    
   and wherein the dynamic routing algorithm identifies individual links to comprise the load - sensitive route based at least on the amount of the bandwidth of those links that has already been allocated to long - lived flows.    
 
     
     
       2. A method of routing packets in a packet-switched network comprising the steps of:
 establishing a static route for packets in the packet-switched network;  
 classifying a first group of packets as a long-lived flow; and  
 establishing a load-sensitive route for the long-lived flow, and  
   routing the long - lived flow over the load-sensitive route,   
 wherein the load-sensitive route is established by creating a label-switched path in MPLS,  
   wherein the establishing a load - sensitive route includes using a dynamic routing algorithm to identify the load - sensitive route,    
   and wherein the dynamic routing algorithm identifies individual links to comprise the load - sensitive route based at least on the amount of the bandwidth of those links that has already been allocated to long - lived flows.    
 
     
     
       3. A router for a packet-switched network comprising:
 a plurality of interfaces to other routers in the packet-switched network for receiving and forwarding packets;  
 packet classifying means for classifying groups of received packets as a long-lived flow; and  
 routing means 
 for computing and forwarding packets along a static route; and  
 for computing and forwarding long-lived flows of packets along a load-sensitive route,  
 wherein flows of long-lived packets are initially routed over the static route and continue to be routed over the static route if a load-sensitive route with adequate capacity cannot be established,  
   wherein the computing and forwarding long - lived flows includes using a dynamic routing algorithm to identify the load - sensitive route,    
   and wherein the dynamic routing algorithm identifies individual links to comprise the load - sensitive route based at least on the amount of the bandwidth of those links that has already been allocated to long - lived flows.    
 
 
     
     
       4. A router for a packet-switched network comprising:
 a plurality of interfaces to other routers in the packet-switched network for receiving and forwarding packets;  
 packet classifying means for classifying groups of received packets as a long-lived flow; and;  
 routing means 
 for computing and forwarding packets along a static route; and  
 for computing and forwarding long-lived flows of packets along a load-sensitive route,  
 wherein the load-sensitive route is established by creating a label-switched path in MPLS,  
   wherein the computing and forwarding long - lived flows includes using a dynamic routing algorithm to identify the load - sensitive route,    
   and wherein the dynamic routing algorithm identifies individual links to comprise the load - sensitive route based at least on the amount of the bandwidth of those links that has already been allocated to long - lived flows.    
 
 
     
     
       5. A non- transitory  computer readable medium containing executable program instructions for performing a method on a router connected to a packet-switched network comprising the steps of:
 establishing a static route for packets in the packet-switched network;  
 classifying a first group of packets as a long-lived flow; and  
 establishing a load-sensitive route for the long-lived flow;  
 wherein flows of long-lived packets are initially routed over the static route and continue to be routed over the static route if a load-sensitive route with adequate capacity cannot be established,  
   wherein the establishing a load - sensitive route includes using a dynamic routing algorithm to identify the load - sensitive route,    
   and wherein the dynamic routing algorithm identifies individual links to comprise the load - sensitive route based at least on the amount of the bandwidth of those links that has already been allocated to long - lived flows.    
 
     
     
       6. A non- transitory  computer readable medium containing executable program instructions for performing a method on a router connected to a packet-switched network comprising the steps of:
 establishing a static route for packets in the packet-switched network;  
 classifying a first group of packets as a long-lived flow; and  
 establishing a load-sensitive route for the long-lived flow;  
 wherein the load-sensitive route is established by creating a label-switched path in MPLS,  
   wherein the establishing a load - sensitive route includes using a dynamic routing algorithm to identify the load - sensitive route,    
   and wherein the dynamic routing algorithm identifies individual links to comprise the load - sensitive route based at least on the amount of the bandwidth of those links that has already been allocated to long - lived flows.    
 
     
     
       7. A method of routing packets in a packet- switched network comprising:      establishing a static path in the packet - switched network;        identifying a group of packets belonging to a long - lived flow, where the long - lived flow was initially routed over the static path; and        responsive to the identifying, routing the long - lived flow over a second path in the packet - switched network that is different from the static path;        wherein the routing includes using a dynamic routing algorithm to identify the second path;        and wherein the dynamic routing algorithm identifies individual links to comprise the second path based at least on the amount of the bandwidth of those links that has already been allocated to long - lived flows.     
     
     
       8. The method of  claim 7  wherein one or more links in the packet network each has a portion of its bandwidth partitioned for long- lived flows.   
     
     
       9. A method of routing packets in a packet- switched network comprising:      establishing a static path in the packet - switched network;      identifying a group of packets belonging to a long- lived flow, where the long - lived flow was initially routed over the static path; and      responsive to the identifying, routing the long- lived flow over a second path in the packet - switched network that is different from the static path;        wherein one or more links in the packet network each has a portion of its bandwidth partitioned for long - lived flows;        and wherein the dynamic routing algorithm identifies individual links to comprise the second path based at least on the amount of the bandwidth of those links partitioned for long - lived flows that has already been allocated.     
     
     
       10. The method of  claim 9  wherein the dynamic routing algorithm identifies as individual links to comprise the second path only links that can accommodate the long- lived flow within the partitioned portion.   
     
     
       11. A method of routing packets in a packet- switched network comprising:      establishing a static path in the packet - switched network;        identifying a group of packets belonging to a long - lived flow, where the long - lived flow was initially routed over the static path; and        responsive to the identifying, routing the long - lived flow over a second path in the packet - switched network that is different from the static path;        wherein the routing includes using a dynamic routing algorithm to identify the second path;        and wherein the dynamic routing algorithm identifies the second path based on link states of links in the packet - switched network wherein the link state of each of at least ones of the links in the packet - switched network is a function of the amount of resources that have been allocated to long - lived flows on that link.     
     
     
       12. A method of routing packets in a packet- switched network comprising:      establishing a static path in the packet - switched network;        identifying a group of packets belonging to a long - lived flow, where the long - lived flow was initially routed over the static path; and        thereafter routing the identified long - lived flow over a path computed using a dynamic routing algorithm if the algorithm is successful in computing a path that meets at least one dynamic routing criterion, but otherwise continuing to route the identified long - lived flow over the static path;        wherein one or more links in the packet network each have a portion of their bandwidths partitioned for long - lived flows;        and wherein the dynamic routing algorithm identifies individual links to comprise the second path based at least on the amount of the bandwidth of those links partitioned for long - lived flows that has already been allocated.     
     
     
       13. A method of routing packets in a packet- switched network comprising:      establishing a static path in the packet - switched network;        identifying a group of packets belonging to a long - lived flow, where the long - lived flow was initially routed over the static path; and        thereafter routing the identified long - lived flow over a path computed using a dynamic routing algorithm if the algorithm is successful in computing a path that meets at least one dynamic routing criterion, but otherwise continuing to route the identified long - lived flow over the static path;        wherein the dynamic routing algorithm identifies the second path based on link states of links in the packet - switched network, and wherein the link state of each of at least ones of the links in the packet - switched network is a function of the amount of resources that have been allocated to long - lived flows on that link.     
     
     
       14. A router for a packet- switched network, the router being adapted to      establish a static path in the packet - switched network;        identify a group of packets belonging to a long - lived flow, where the long - lived flow was initially routed over the static path; and        responsive to the identifying, route the long - lived flow over a second path in the packet - switched network that is different from the static path;        wherein the router uses a dynamic routing algorithm to identify the second path,        and wherein the dynamic routing algorithm identifies individual links to comprise the second path based at least on the amount of the bandwidth of those links that has already been allocated to long - lived flows.     
     
     
       15. A non- transitory computer readable medium containing executable program instructions that, when executed, perform the method comprising      establishing a static path in the packet - switched network;        identifying a group of packets belonging to a long - lived flow, where the long - lived flow was initially routed over the static path; and        thereafter routing the identified long - lived flow over a path computed using a dynamic routing algorithm if the algorithm is successful in computing a path that meets at least one dynamic routing criterion, but otherwise continuing to route the identified long - lived flow over the static path;        wherein one or more links in the packet network each have a portion of their bandwidths partitioned for long - lived flows and wherein the dynamic routing algorithm identifies individual links to comprise the second path based at least on the amount of the bandwidth of those links partitioned for long - lived flows that has already been allocated.     
     
     
       16. A non- transitory computer readable medium containing executable program instructions that, when executed, perform the method comprising      establishing a static path in the packet - switched network;        identifying a group of packets belonging to a long - lived flow, where the long - lived flow was initially routed over the static path; and        thereafter routing the identified long - lived flow over a path computed using a dynamic routing algorithm if the algorithm is successful in computing a path that meets at least one dynamic routing criterion, but otherwise continuing to route the identified long - lived flow over the static path;        wherein the dynamic routing algorithm identifies the second path based on link states of links in the packet - switched network, and wherein the link state of each of at least ones of the links in the packet - switched network is a function of the amount of resources that have been allocated to long - lived flows on that link.