Method and apparatus for indicating congestion in a source routed network

Abstract

A packet header in a source routed network is augmented to include, with each hop identifier, at least one bit for indicating congestion at the particular hop. As the packet traverses from the source to the destination, when congestion is detected at a hop, a congestion bit associated with the hop is set in the header. At the destination, when another packet is forwarded from the destination to the source on the same path, the congestion bits are reflected back to the source. When the source receives the congestion bits, it has the option of re-routing subsequent communications between the source and destination nodes by generating a new hop list, which routes around one or more of the congested hops.

1 . A method of routing packets in a source-routed data network, the method comprising:
 at a source node:
 determining a first route to a destination node using a routing protocol; 
 encoding the first route into a first packet addressed to the destination node; 
 forwarding the first packet toward the destination node along the first route; 
 receiving a second packet from the destination node, the second packet containing information indicative of congestion along the first route; 
 determining a second route to the destination node based on the information indicative of congestion along the first route. 
   
     
     
         2 . The method of  claim 1 , wherein:
 the first route comprises a plurality of hops between the source node and the destination node, and the information indicative of congestion identifies congestion on at least one hop of the plurality of hops; and   determining the second route comprises determining the second route to avoid the congestion on the at least one hop.   
     
     
         3 . The method of  claim 2 , wherein:
 encoding the first route into the first packet addressed to the destination node comprises adding a hop identifier for the at least one hop of the first route to the first packet; and   the first packet comprises a respective congestion information field associated with the hop identifier.   
     
     
         4 . The method of  claim 3 , wherein the second packet received from the destination node comprises a hop identifier for each hop of the first route and a respective congestion information field associated with each hop identifier, content of each congestion information field indicating a level of congestion on an associated hop of the first route. 
     
     
         5 . The method of  claim 1 , further comprising:
 at an intermediate node between the source node and the destination node on the first route:
 receiving the first packet forwarded from the source node; 
 adding information to the first packet indicating congestion at the intermediate node; and 
 forwarding the first packet with the information to a next node along the first route. 
   
     
     
         6 . The method of  claim 5 , wherein:
 the first route comprises a plurality of hops between the source node and the destination node;   the first packet comprises a hop identifier for each hop of the first route and a respective congestion information field associated with each hop identifier; and   adding information to the first packet indicating congestion at the intermediate node comprises putting a value indicative of congestion in the respective congestion information field associated with the hop identifier associated with the intermediate node.   
     
     
         7 . The method of  claim 1 , further comprising:
 at the destination node:
 receiving the first packet forwarded on the first route; 
 reading information indicative of congestion along the first route from the first packet; 
 inserting the information indicative of congestion along the first route into the second packet to be forwarded from the destination node to the source node; and 
 forwarding the second packet containing the information indicative of congestion toward the source node. 
   
     
     
         8 . The method of  claim 7 , wherein:
 the first route comprises a plurality of hops between the source node and the destination node;   the first packet forwarded toward the destination node along the first route comprises a hop identifier for each hop of the first route and a respective congestion information field associated with each hop identifier; and   reading the information indicative of congestion along the first route comprises reading the congestion information field associated with each hop identifier.   
     
     
         9 . The method of  claim 8 , wherein:
 the second packet to be forwarded from the destination node to the source node comprises a hop identifier for each hop of the first route and a respective congestion information field associated with each hop identifier;   inserting the information indicative of congestion along the first route comprises inserting information corresponding to the information read from each congestion information field of the first packet forwarded along the first route into a corresponding congestion information field of the second packet to be forwarded from the destination node to the source node.   
     
     
         10 . The method of  claim 1 , wherein:
 the first route comprises a plurality of hops between the source node and the destination node;   the first packet forwarded toward the destination node along the first route comprises a hop identifier for each hop of the first route and a respective congestion information field associated with each hop identifier, each congestion information field comprising a forward congestion information sub-field and a reverse congestion information sub-field; and   the method further comprises:
 at each node intermediate to the source node and the destination node along the first route, when there is congestion at the intermediate node, putting a value indicative of the congestion in the forward congestion information sub-field associated with the hop identifier associated with the intermediate node; and 
 at the destination node:
 receiving the first packet forwarded on the first route; 
 inserting the information indicative of congestion along the first route read from the forward congestion sub-fields of the first packet into corresponding reverse congestion sub-fields of the second packet to be forwarded from the destination node to the source node; and 
 forwarding the first packet containing the congestion information inserted in the reverse congestion sub-fields toward the source node. 
 
   
     
     
         11 . A system for routing packets in a source-routed data network, the system comprising:
 a source node comprising:
 routing logic operable to determine a first route to a destination node using a routing protocol; 
 encoding logic operable to encode the first route into a first packet addressed to the destination route; 
 forwarding logic operable to forward the first packet toward the destination node along the first route; and 
 at least one packet receive buffer operable to receive a second packet from the destination node, the second packet containing information indicative of congestion along the first route; 
 the routing logic being further operable to determine a second route to the destination node based on the information indicative of congestion along the first route. 
   
     
     
         12 . The system of  claim 11 , wherein:
 the first route comprises a plurality of hops between the source node and destination node;   the at least one packet receive buffer is operable to receive a packet containing information indicative of congestion along the first route by receiving a packet indicative of congestion on at least one hop of the first route; and   the routing logic is operable to determine the second route by determining the second route that avoids congestion on the at least one hop of the first route.   
     
     
         13 . The system of  claim 12 , wherein:
 the encoding logic is operable to encode the first route into the first packet addressed to the destination node by adding a hop identifier for each hop of the first route to the first packet; and   the first packet forwarded toward the destination node along the first route comprises a respective congestion information field associated with each flop identifier.   
     
     
         14 . The system of  claim 13 , wherein the second packet received from the destination node comprises a hop identifier for each hop of the first route and a respective congestion information field associated with each hop identifier, content of each congestion information field indicating a level of congestion on an associated hop of the first route. 
     
     
         15 . The system of  claim 11 , further comprising:
 at least one intermediate node between the source node and the destination node on the first route, each intermediate node being operable:
 to receive the first packet forwarded from the source node; 
 to add information to the first packet indicating congestion when there is congestion at the each intermediate node; and 
 to forward the first packet with the information to a next node along the first route. 
   
     
     
         16 . The system of  claim 15 , wherein:
 the first route comprises a plurality of hops between the source node and destination node;   the first packet forwarded toward the destination node along the first route comprises a hop identifier for each hop of the first route and a respective congestion information field associated with each hop identifier; and   each intermediate node is operable to add information to the first packet indicating congestion when there is congestion at the intermediate node by putting a value indicative of congestion in a congestion information field associated with the hop identifier associated with the intermediate node.   
     
     
         17 . The system of  claim 11 , further comprising a destination node operable:
 to receive the first packet forwarded on the first route;   to read the information indicative of congestion along the first route from the first packet;   to insert the information indicative of congestion along the first route into the second packet to be forwarded from the destination node to the source node; and   to forward the second packet containing the information indicative of congestion toward the source node.   
     
     
         18 . The system of  claim 17 , wherein:
 the first route comprises a plurality of hops between the source node and the destination node;   the first packet forwarded toward the destination node along the first route comprises a hop identifier for each hop of the first route and a respective congestion information field associated with each hop identifier; and   the forwarding logic is operable to read the information indicative of congestion along the first route by reading the respective congestion information field associated with each hop identifier.   
     
     
         19 . The system of  claim 18 , wherein:
 the second packet to be forwarded from the destination node to the source node comprises a hop identifier for each hop of the first route and a respective congestion information field associated with each hop identifier;   the forwarding logic of the destination node is operable to insert the information indicative of congestion along the first route by inserting the information corresponding to the information read from each congestion information field of the first packet forwarded along the first route into a corresponding congestion information field of the second packet to be forwarded from the destination node to the source node.   
     
     
         20 . The system of  claim 11 , wherein:
 the first route comprises a plurality of hops between the source node and the destination node;   the first packet forwarded toward the destination node along the first route comprises a hop identifier for each hop of the first route and a respective congestion information field associated with each hop identifier, each congestion information field comprising a forward congestion information sub-field and a reverse congestion information sub-field; and   the system further comprises:
 at least one node intermediate to the source node and the destination node along the first route, each intermediate node being operable, when there is congestion at the intermediate node, to put in the first packet a value indicative of congestion in a forward congestion information sub-field associated with a hop identifier, the hop identifier being associated with the intermediate node; and 
 the destination node operable:
 to receive the first packet forwarded on the first route; 
 to insert the information indicative of congestion along the first route read from the forward congestion sub-fields of the first packet into corresponding reverse congestion sub-fields of the second packet to be forwarded from the destination node to the source node; and 
 to forward the second packet containing the congestion information inserted in the reverse congestion sub-fields toward the source node.