Abstract:
In general, in one aspect, the disclosure describes a technique of determining forwarding information for at least a sub-set of members of a multicast group, and sending, toward a downstream entity, at most a single copy of data to be multicasted to the sub-set of members and the determined forwarding information.

Description:
BACKGROUND  
         [0001]    Networks enable computers and other devices to communicate. For example, networks can carry data representing video, audio, e-mail, and so forth. Typically, data sent across a network is divided into smaller messages. The structure and contents of the messages depend on the networking technology being used. For example, Internet Protocol (IP) datagrams include a destination address that is much like an address written on the outside of an envelope. Devices, known as routers, receive datagrams and can determine how to forward the datagram further toward its destination based on the destination address. Another network technology is known as Asynchronous Transfer Mode (ATM). In ATM, data messages, known as cells, include identification of a “circuit” that leads from the sender to the receiver. That is, rather than identifying a destination, an ATM cell identifies a path connecting the sender and receiver.  
           [0002]    To complicate matters conceptually, IP and ATM can both be used to support the other technology. For example, an IP datagram can be divided across different ATM cells. A receiver can reassemble the IP datagram after receiving the ATM cells.  
           [0003]    IP datagrams and ATM cells are examples of protocol data units (PDUs). A PDU includes a payload and header. The data in the header is often used by network protocols in handling the PDU (e.g., determining where to forward the PDU, whether transmission errors occurred, and so forth). Other examples of PDUs include frames (e.g., Ethernet and Synchronous Optical Network (SONET) frames) and segments (e.g., Transmission Control Protocol (TCP) segments).  
           [0004]    A sender can send data to a single receiver. This is known as “unicasting”. Alternately, a sender (or multiple senders) can send the same data to multiple members of a group. For example, a sender can send streaming video data to many different group members located at different points in the network. This is known as “multicasting”.  
           [0005]    Different protocols support multicasting in different ways. For example, in the Internet Protocol, instead of specifying a single destination, an IP datagram can specify a group address. ATM networks may also support multicasting in a variety of ways. For example, multicasting may be provided by a “tree” of circuits where a given circuit may feed diverging circuits downstream. Again, the above is merely a sampling of a wide variety of approaches to multicasting. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0006]    [0006]FIG. 1 is a diagram illustrating handling of multicast data.  
         [0007]    [0007]FIG. 2 is a diagram illustrating control and multicast data.  
         [0008]    [0008]FIG. 3 is a diagram illustrating data identifying different multicast group sub-groups.  
         [0009]    [0009]FIG. 4 is a diagram of logic to transmit multicast data via egress interfaces.  
         [0010]    [0010]FIG. 5 is a diagram illustrating interface scheduling.  
         [0011]    [0011]FIG. 6 is a flow-chart of a process for multicasting data.  
         [0012]    [0012]FIG. 7 is a diagram of a network processor. 
     
    
     DETAILED DESCRIPTION  
       [0013]    Multicasting can increase traffic handled by network devices. For example, where paths to different multicast group members diverge, a device may need to construct multiple protocol data units (PDUs) (e.g., IP datagrams or ATM cells) having copies of the same multicast data, but destined for different group members. FIG. 1 illustrates a technique that can potentially reduce traffic associated with multicasting. In particular, the technique shown can delay replication of multicast data to reduce traffic between a device  100  and a downstream device  106 . As shown, instead of carrying multiple PDUs storing copies of the same multicast data  104  between devices  100  and  106 , FIG. 1 depicts a scheme where device  100  transmits one copy of the multicast data  104  with control data  102 . The downstream device  106 , in turn, generates PDUs carrying the multicast data and transmits the generated PDUs via the appropriate egress interfaces (e.g., links to remote network devices). The technique illustrated in FIG. 1 may not only reduce traffic between devices  100  and  106 , but may also offload duties from device  100 . For example, construction of the out-bound PDUs by the downstream device  106  can conserve resources of device  100 .  
         [0014]    In greater detail, the sample system of FIG. 1 includes a device  100 , such as a network processor or an Application-Specific Integrated Circuit (ASIC), that processes PDUs received over a network. The processing can include a determination of how to forward a PDU. For example, a network processor may be programmed to determine which egress interface(s) (labeled “port 1”-“port n”) of a downstream device  106  to send out received multicast data. The downstream device  106  shown in FIG. 1 may be local to device  100 . For example, the device  106  may be a medium access controller (MAC) (e.g., an Ethernet MAC), SONET framer, or other link layer device. Alternately, the downstream device  106  may be a remote device (i.e., one separated from device  100  by one or more network connections).  
         [0015]    As shown in FIG. 1, the device  100  transmits multicast data  104  (e.g., the payload(s) of one or more received multicast PDUs) to the downstream device  106 . The device  100  also transmits control information  102  that instructs the downstream device  106  how to handle multicast data  104 . For example, as shown, the control information  102  includes forwarding information such as identification of the downstream device  106  egress interfaces that should be used to transmit the multicast data. In the example shown, the control information  102  also includes PDU header data. The downstream device  106  can generate multiple out-bound PDUs  108  by adding (e.g., pre-pending) the headers to copies of the multicast data  104 . The downstream device  106  can then transmit the generated PDUs  108  via the identified egress interfaces.  
         [0016]    The network device  100  can store the control information  102  for a multicast group to speed PDU processing. For example, the device  100  may store a table of headers and interfaces to be used for members of different multicast groups (or sub-groups). Thus, determining the control information  102  becomes a matter of a fast table lookup. The network device  100  may be statically provisioned with the control information  102  or may update the control information  102  as members join and leave a multicast group. For example, the network device  100  may receive group membership data transmitted via IGMP (Internet Group Management Protocol) messages from group members and multicast routers or switches. Additionally, the device  100  may also dynamically modify the control information  102  based on changing network characteristics (e.g., as network connections become congested or go off-line).  
         [0017]    Network device  100  may perform other operations beyond determining the control information  102  for given multicast data. For example, the device  100  can facilitate multicasting of an IP datagram over an ATM network by segmenting the datagram data across different ATM cells. Techniques for associating ATM circuits with IP multicast groups is described in greater detail in Request For Comments (RFC) 2022 (G. Armitage, Support for Multicast over UNI 3.0/3.1 based ATM Networks, November 1996).  
         [0018]    In the sample scheme depicted in FIG. 1, the limited responsibilities of the downstream device  100  enable the device to be implemented relatively inexpensively (e.g., as a Field Programmable Gate Array (FPGA) or other circuitry). The division of duties can also conserve resources of the network device  100 . That is, instead of expending resources replicating PDUs, the device  100  can devote greater resources to other PDU processing tasks. Again, the technique illustrated above can also reduce traffic between device  100  and  106  as the multicast data  104  may be transmitted, at most, once for a given multicast group or sub-group.  
         [0019]    [0019]FIG. 2 illustrates an example of control  120  and multicast data  122  messages sent to the downstream device  106 . As-shown, both messages  120 ,  122  include a “type” identifier to distinguish data messages  122  from control messages  120 . Both messages also include a multicast group identifier that enables the downstream device  106  to pair the messages  120 ,  122  together.  
         [0020]    The data message  122  includes the data being multicast. This data can include the payload of a multicast PDU received by device  100  and may or may not include portions of the received PDU header. The control message  120  can include data for the different paths to be taken by copies of the multicast message. For example, as shown, the message  120  includes pairs of headers/egress interfaces. For example, the pairs may include Virtual Path Identifiers (VPI) and a Virtual Channel Identifiers (VCI) of an ATM header and port or virtual port identifiers. After receiving the messages  120 ,  122  the downstream device  106  can construct the out-bound PDUs by copying the multicast data and adding the header data. The device  120  can then output the constructed PDUs via the identified egress interfaces.  
         [0021]    The messaging scheme shown in FIG. 2 is merely illustrative and many variations of the above can be implemented. For instance, instead of sending two different messages  120 ,  122 , a single message can be used that includes both control and multicast data.  
         [0022]    Potentially, members of a multicast group may have different associated data rates. For example, some multicast group members may have a data rate associated with Digital Subscriber Loop (DSL) connections while others have data rates associated with T1 connections. As shown in FIG. 3, the device  100  can categorize different multicast group  112  members according to their different data rates  114 . In the example illustrated, multicast group  112   x  includes data rate sub-groups  114   a ,  114   n . As shown, the control data stored for members of a sub-group  114   a ,  114   n  can include identification (e.g., port numbers or Ethernet addresses) of the downstream egress interfaces used to transmit a multicast message to the sub-group  114  members and/or header data used to prepare the out-bound PDUs at the downstream device  106 . For instance, for sub-group  114   a , multicast data  110  should be output via downstream ports “2”, “1”, and “3”.  
         [0023]    As shown, device  100  can transmit control data  114   a  to the downstream device  106  for individual data rate sub-groups. Transmitting control information  114   a  and multicast  110  data, at most, once per sub-group enables the downstream device  106  to efficiently handle transmission of the multicast data. Additionally, when multicast data is being sent to multiple sub-groups, the device  100  can flag the multicast data for storage by the downstream entity  106 . This can eliminate retransmission of the multicast data to the downstream entity  106  for each sub-group. As described below, grouping members by data rate can also potentially ease transmission scheduling and can reduce system complexity.  
         [0024]    [0024]FIG. 4 illustrates a scheme that device  100  can implement to coordinate efficient handling of multicast data via the downstream device  106 . As shown, when data arrives at the device, receive logic  130  determines whether the data is a unicast or multicast transmission and enters a request to transmit the data in the appropriate queue  132 ,  134 . For multicast data, an entry can be queued in a multicast queue  134  for each multicast sub-group.  
         [0025]    A scheduler  138  determines when the set of egress interfaces used to multicast to a sub-group are available. At the time scheduled, transmit logic  136  sends the multicast and control data to the downstream device. The downstream device  106  can then generate the specified PDUs and output them via the egress interfaces.  
         [0026]    [0026]FIG. 5 illustrates an example of a scheduling scheme that synchronizes availability of the egress interfaces used by a particular multicast group or sub-group. The scheme includes a interface vector for each multicast group or data rate sub-group receiving multicast data. A bit (labeled “intf #”) within the vector identifies the availability of an egress interface. Initially, the vector may be setup so that bits corresponding to the egress interfaces to be used to transmit multicast data are set to “0” while the remaining vector bits are set to “1”. In the example shown, the multicast data will be transmitted via interfaces “1” and “3”.  
         [0027]    The scheme also includes an interface “wheel” that identifies when egress interfaces will become available for a transmission. As shown, in a given time-period (e.g., a set of downstream device cycles), illustrated as a pie-slice of the wheel, one or more interfaces may be scheduled for availability. For instance, in time-period “2”  144   b  egress interface “1” will become available, for example, after completing transmission of a previously scheduled PDU and awaiting some minimum gap time between transmissions. Thus, for time-period “2”, the bit for interface “1” is set to “1” and the use of interface “1” is reserved (e.g., the interface cannot be scheduled for other unicast or multicast use until the multicast data is transmitted). Finally, in time-period “3”  144   c , egress interface “3” will become available and the bit for interface “3” is set to “1”. Thus, at time-period “3”, all bits in the vector are set. Thus, the needed interfaces have been reserved for the multicast sub-group. A schedule entry (e.g., the multicast ID) can be made for the sub-group at the specified time. Other entries identify other scheduled multicast groups/sub-groups and unicast transmissions. When time-period “3”, arrives, the schedule entry causes the device  100  to transmit the control and multicast data to the downstream device.  
         [0028]    The interface wheel is continually updated to reflect the future availability of interfaces. Thus, entries for interfaces “1” and “3” can be re-inserted into the wheel after time-period “3” based on the size and data rate of the transmission. Since the sub-groups may be based on data rate, the technique described above can keep the interfaces synchronized after the initial synchronization. That is, since the interfaces are operated at the same rate and may transmit the same amount of data, the interfaces may be scheduled at the same future time-periods. This can ease scheduling operations.  
         [0029]    The scenarios illustrated above assumed that a given set of interfaces could be reserved within a given period of time. However, such scheduling may not always be possible. In such cases, the multicast transmissions to the different interfaces may be enqueued in unicast queues.  
         [0030]    Provisioning bandwidth for the multicast traffic may be performed. Since the constituent ports in the multicast group may be of different rates, apportioning bandwidth for the multicast group can ensure the minimum bandwidth requirement at each port to process the multicast stream. The definition of minimum bandwidth for multicast traffic may be defined in cases where such traffic contains real-time data (video). For multicast traffic that is processed at best-effort priority, the scheduler performs a different set of operations compared to multicast groups that have bandwidth associated with it. The scheduler distinguishes between unicast and multicast traffic. For multicast traffic, if a minimum bandwidth is assigned to a multicast group, a unique ID associated with the multicast group will be used to populate the scheduler wheel. A schedule entry for unicast traffic will contain an index to the unicast queue and for multicast traffic, a schedule entry will index into a table of bit-vectors. The significance of the bit-vector is to be able to identify the physical ports that are eligible for transmission. To determine the eligibility of each physical port in the multicast group, the scheduler will use the physical port&#39;s inter-packet/cell gap along with other schedule information of other packets/cells on that port. The scheduler then reconciles the time when the multicast packet/cell needs to be sent to meet the minimum bandwidth (of the multicast group&#39;s bandwidth) criteria with the physical port bandwidth. For ports that are eligible, the bit-vector associated with the multicast group will be updated. For ports that cannot be reconciled, the multicast packet will be en-queued into the unicast queue since such ports will not be able to transmit that multicast packet along with other ports in the multicast group.  
         [0031]    If multicast packets/cells are sent with a best-effort priority, the scheduler will determine when ports in the multicast group become eligible and, based on this information, it will group a subset of multicast group physical ports for transmission. If such an alignment of transmission time among some subset of the physical ports in the multicast group is not possible, the multicast packet is replicated and copied into the respective unicast queues.  
         [0032]    Packet/cell replication may be avoided by using a virtual queue concept, where a packet is not removed from a queue until the packet is transmitted among all the members of the multicast group.  
         [0033]    [0033]FIG. 6 depicts a flow-chart illustrating operation of the sample system described above. After receiving  152  data to multicast to a multicast group, forwarding information for the message is determined  154  (e.g., egress interfaces of the downstream device and PDU headers). After receiving  160  the transmitted multicast  156  and control data  158 , the downstream device can construct PDUs and forward  162  the PDUs via the appropriate egress interfaces based on the control information.  
         [0034]    The techniques described above may be used in a wide variety of systems. For example, FIG. 7 depicts a programmable network processor  200  that features multiple packet processors  204 . The network processor  200  shown is an Intel® Internet eXchange network Processor (IXP). Other network processors feature different designs.  
         [0035]    As shown, the network processor  200  features an interface  202  (e.g., an Internet eXchange bus interface) that can carries PDUs between the processor  200  and network components. For example, the bus may carry PDUs received via physical layer (PHY) components (e.g., wireless, optic, or copper PHYs) and link layer component(s)  222  (e.g., MACs and framers). The processor  200  also includes an interface  208  for communicating, for example, with a host. Such an interface may be a Peripheral Component Interconnect (PCI) type interface such as a PCI-X bus interface. The processor  200  also includes other components such as memory controllers  206 ,  212 , a hash engine, and scratch pad memory.  
         [0036]    The network processor  200  shown features a collection of packet processors  204 . The packet processors  204  may be Reduced Instruction Set Computing (RISC) processors tailored for network PDU processing. For example, the packet processors may not include floating point instructions or instructions for integer multiplication or division commonly provided by general purpose central processing units (CPUs).  
         [0037]    An individual packet processor  204  may offer multiple threads. The multi-threading capability of the packet processors  204  is supported by context hardware that reserves different general purpose registers for different threads and can quickly swap instruction and status data for the different threads between context registers and context storage.  
         [0038]    The processor  200  also includes a core processor  210  (e.g., a StrongARM® XScale®) that is often programmed to perform “control plane” tasks involved in network operations. The core processor  210 , however, may also handle “data plane” tasks and may provide additional datagram processing threads.  
         [0039]    The network processor  200  may implement the techniques described above in a variety of ways. For example, the control data may be stored as an array in DRAM while different packet processor  204  and core  210  threads process received PDUs and implement scheduling logic.  
         [0040]    The techniques may be implemented in hardware, software, or a combination of the two. For example, the techniques may be implemented by programming a network processor or other processing system. The programs may be disposed on computer readable mediums and include instructions for causing processor(s) to execute instructions implementing the techniques described above.  
         [0041]    Other embodiments are within the scope of the following claims.