Method for multicast distribution tree switchover

Abstract

Described are a method and a device for efficiently switching multicast data flows from a shared distribution tree to a shortest path distribution tree. The method achieves an efficient and scalable tree switch that reduces the latency of multicast data transmitted from the source to receivers. A determination is made for each source group (S,G) entry in a portion of a forwarding plane database of a router as to whether a byte count for that entry exceeds a threshold value. A message sent from the forwarding plane to the router control plane indicates the (S,G) entries determined to have byte counts exceeding the respective threshold values. For each message entry, the respective shared distribution tree is switched to a shortest path distribution tree. The method achieves a substantial reduction in the number of inter-process messages exchanged between the control plane and the forwarding plane compared to conventional tree switchover techniques.

1. A method for transmitting multicast data through a network, the method comprising:
 receiving, in a forwarding plane of a router, a plurality of multicast data flows, each multicast data flow comprised of multicast data packets, each multicast data flow being routed through a shared distribution tree in a network and having a corresponding source group (S,G) entry stored in a database of the forwarding plane; 
 determining, in the forwarding plane of the router, whether a byte count for each (S,G) entry exceeds a respective threshold value; 
 sending an inter-process message from the forwarding plane to a control plane of the router in response to a determination that (S,G) entries have a byte count that exceeds the respective threshold value, the inter-process message indicating the (S,G) entries for the multicast data flows that are determined to have byte counts that exceed the respective threshold values, the inter-process message being a separate communication from the multicast data packets; and 
 switching from the shared distribution tree to a shortest path distribution tree for each multicast data flow having a corresponding (S,G) entry that is indicated in the inter-process message. 
 
     
     
       2. The method of  claim 1  wherein a byte count is determined by examining a byte counter in the forwarding plane for a timer interval. 
     
     
       3. The method of  claim 1  wherein the threshold value is programmable. 
     
     
       4. The method of  claim 1  wherein the corresponding (S,G) entries are a portion of all the (S,G) entries stored in the database. 
     
     
       5. The method of  claim 1 , wherein determining, in the forwarding plane of the router, whether a byte count for each (S,G) entry exceeds a respective threshold value includes examining at least a portion of (S,G) entries stored in the database of the forwarding plane prior to sending the inter-process message to the control plane. 
     
     
       6. The method of  claim 5 , wherein sending the inter-process message from the forwarding plane to the control plane includes the forwarding plane sending the inter-process message in lieu of the control plane polling the forwarding plane to determine byte counts. 
     
     
       7. The method of  claim 6 , wherein a byte count is determined by examining a byte counter in the forwarding plane for a timer interval, wherein the corresponding (S,G) entries are a portion of all the (S,G) entries stored in the database, and wherein the threshold value is programmable. 
     
     
       8. The method of  claim 7 , further comprising different respective threshold values for each of the (S,G) entries. 
     
     
       9. A router for routing multicast data packets through a network, comprising:
 a forwarding plane of the router, comprising:
 a multicast forwarding database storing a plurality of source group (S,G) entries each corresponding to a multicast data flow received in the forwarding plane of the router; and 
 a plurality of byte counters, each byte counter determining a byte count for one of the multicast data flows corresponding to one of the (S,G) 
 
 entries for a time interval; and 
 a control plane of the router in communication with the forwarding plane, the control plane receiving an inter-process message from and initiated by the forwarding plane indicating (S,G) entries of the multicast data flows for which a corresponding byte count exceeds a respective threshold value, wherein the control plane initiates a tree distribution switchover for each multicast data flow having a corresponding (S,G) entry indicated in the inter-process message, the inter-process message being a separate communication from the multicast data packets. 
 
     
     
       10. The router of  claim 9  wherein the tree distribution switchover comprises switching from a shared distribution tree to a shortest path distribution tree. 
     
     
       11. The router of  claim 9  wherein the forwarding plane further comprises a timer module to initiate the sending of the message from the forwarding plane to the control plane upon expiration of a timer interval. 
     
     
       12. The router of  claim 9  wherein the forwarding plane further comprises a buffer to store information indicating the (S,G) entries of the multicast data flows for which the byte count exceeds the respective threshold value. 
     
     
       13. The router of  claim 9  wherein the message from the forwarding plane indicates a portion of the (S,G) entries stored in the multicast forwarding database for which the byte count of the multicast data flow exceeds the respective threshold value. 
     
     
       14. The router of  claim 9 , wherein the forwarding plane further comprises examining at least a portion of (S,G) entries stored in the database of the forwarding plane prior to sending the inter-process message to the control plane. 
     
     
       15. The router of  claim 14 , wherein the forwarding plane further comprises sending the inter-process message to the control plane in lieu of the control plane polling the forwarding plane to determine byte counts. 
     
     
       16. The router of  claim 15 , wherein the tree distribution switchover comprises switching from a shared distribution tree to a shortest path distribution tree. 
     
     
       17. The router of  claim 16  wherein the forwarding plane further comprises a timer module to initiate the sending of the inter-process message from the forwarding plane to the control plane upon expiration of a timer interval. 
     
     
       18. The router of  claim 17  wherein the forwarding plane further comprises a buffer to store information indicating the (S,G) entries of the multicast data flows for which the byte count exceeds the respective threshold value. 
     
     
       19. The router of  claim 18  wherein the inter-process message from the forwarding plane indicates a portion of the (S,G) entries stored in the multicast forwarding database for which the byte count of the multicast data flow exceeds the respective threshold value.