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 pre-provisioned 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.

What is claimed is:  
     
       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,  
       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.  
     
     
       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,  
       wherein the load-sensitive route is established by creating a label-switched path in MPLS.  
     
     
       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.  
     
     
       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.  
     
     
       5. A 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.  
     
     
       6. A 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.