2003-04-08 Assigned to INTEL CORPORATION reassignment INTEL CORPORATION ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: HOOPER, DONALD F., KALKUNTE, SURESH S.
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.
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.
FIG. 7 is a diagram of a network processor.
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.
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).
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.
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).
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).
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.
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.
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.
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.
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”.
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.
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.
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.
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.
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.
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.
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.
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).
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.
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.
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.
sending, toward the downstream entity, at most a single copy of data to be multicasted to the sub-set of members and the determined forwarding information.
2. The method of claim 1, further comprising transmitting, from the downstream entity, multiple copies of the data to be multicasted via the downstream device egress interfaces identified by the forwarding information.
3. The method of claim 1, wherein the sub-set comprises a sub-group of members of a multicast group sharing a data rate.
4. The method of claim 1, further comprising sending, to the downstream entity, data of multiple protocol data unit headers.
5. The method of claim 4, further comprising, at the downstream entity, constructing multiple protocol data units using the multicast data and the data of multiple protocol data unit headers.
6. The method of claim 5, wherein the protocol data units include an Asynchronous Transfer Mode (ATM) cell having a header than includes a Virtual Path Identifier (VPI) and a Virtual Channel Identifier (VCI).
7. The method of claim 1, further comprising scheduling transmission via the multiple egress interfaces.
8. The method of claim 7, wherein the scheduling comprises synchronizing scheduling of egress interfaces used to carry PDUs to group members sharing a data rate.
9. The method of claim 7, wherein the scheduling comprises scheduling in accordance with bandwidth provisioned to the multicast group.
10. The method of claim 1, wherein the downstream device comprises a link layer device.
11. The method of claim 10, wherein the link layer device comprises a medium access controller (MAC).
12. The method of claim 1, further comprising storing control data for different multicast group sub-groups, the control data at least identifying egress interfaces for members of the multicast sub-groups.
send, toward the downstream entity, at most a single copy of data to be multicasted to the sub-set of members and the determined forwarding information.
14. The device of claim 13, wherein the sub-set comprises a sub-group of members of a multicast group sharing a data rate.
15. The device of claim 13, further comprising logic to send, to the downstream entity, data of multiple protocol data unit headers.
16. The device of claim 15, wherein the headers comprise headers for Asynchronous Transfer Mode (ATM) cells than include a Virtual Path Identifier (VPI) and a Virtual Channel Identifier (VCI).
17. The device of claim 13, further comprising logic to schedule transmission via the multiple egress interfaces.
18. The device of claim 17, wherein the logic to schedule comprises logic to synchronize scheduling of egress interfaces used to carry PDUs to group members sharing a data rate.
19. The device of claim 17, wherein the logic to schedule comprises logic to schedule in accordance with bandwidth provisioned to the multicast group and rates of the egress interfaces.
20. The device of claim 19, wherein the multicast group is configured to operate in best-effort mode.
21. The device of claim 13, wherein the downstream device comprises a link layer device.
22. The device of claim 13, further comprising memory storing control data for different multicast group sub-groups, the control data at least identifying egress interfaces for members of the multicast sub-groups.
23. The device of claim 13, wherein the logic comprises multiple Reduced Instruction Set Computing (RISC) processors programmed to implement the logic.
transmit the data to be multicasted via more than one egress interface based on the forwarding information.
25. The device of claim 24, wherein the forwarding information comprises forwarding information corresponding to a sub-group of members of a multicast group sharing a data rate.
26. The device of claim 24, further comprising logic to receive multiple protocol data unit headers.
27. The device of claim 26, further comprising logic to construct multiple protocol data units using the multicast data and the data that identifies multiple protocol data unit headers.
28. The device of claim 27, wherein the protocol data units include an Asynchronous Transfer Mode (ATM) cell having a header than includes a Virtual Path Identifier (VPI) and a Virtual Channel Identifier (VCI).
30. The computer program of claim 29, wherein the sub-set comprises a sub-group of members of a multicast group sharing a data rate.
31. The computer program of claim 29, further comprising instructions to cause the processor to send, toward the downstream entity, data that identifies multiple protocol data unit headers.
32. The computer program of claim 29, further comprising instructions for causing a processor to schedule transmission via the multiple egress interfaces.
33. The computer program of claim 32, wherein the instructions for causing the processor to schedule comprise instructions that cause the processor to synchronize scheduling of egress interfaces used to carry PDUs to group members sharing a data rate.
34. The computer program of claim 32, wherein the instructions for causing the processor to schedule transmission comprise instructions for causing the processor to schedule transmission in accordance with bandwidth provisioned to the multicast group.
35. The computer program of claim 29, wherein the instructions to cause the processor to send the multicast data to the downstream entity comprise instructions to cause the processor to send the multicast data, at most, once per sub-group.
transmit the data to be multicasted via the egress interfaces identified by the forwarding information.
wherein the Ethernet medium access controller logic comprises logic to construct multiple protocol data units from the data to be multicasted and the data for multiple protocol data unit headers.
38. The system of claim 36, wherein the at least a sub-set of member of a multicast sub-group comprise members of a multicast group sharing a data rate.
39. The system of claim 36, wherein the instructions comprise instructions to synchronize scheduling of transmission via the multiple egress interfaces.