Multicast packet duplication at random node or at egress port with frame synchronization

• US 6,751,219 B1
• Filed: 04/20/2000
• Issued: 06/15/2004
• Est. Priority Date: 04/20/2000
• Status: Expired due to Fees

• Current Assignee: Aztech Partners, Inc.
• Original Assignee: Aztech Partners, Inc.
• Inventors: Lipp, Robert J., Boura, Younes
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): Philpott, Justin M
• Application Number:
  US09/553,500
• Time in Patent Office: 1,517 Days
• Field of Search: 370/270, 370/356, 370/390, 370/392, 370/395.51, 370/400, 370/406, 370/408
• US Class Current: 370/390
• CPC Class Codes: H04J 2203/0019 Multicast/broadcast capabilities
• CPC Class Codes: H04J 2203/0023 Routing/path finding
• CPC Class Codes: H04J 2203/008 Support of video
• CPC Class Codes: H04J 3/0623 Synchronous multiplexing systems, e.g. synchronous digital hierarchy/synchronous optical network (SDH/SONET), synchronisation with a pointer process
• CPC Class Codes: H04J 3/1617 carrying packets or ATM cells
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/252 Store and forward routing
• CPC Class Codes: H04Q 11/0005 Switch and router aspects
• CPC Class Codes: H04Q 2011/0047 Broadcast; Multicast

Abstract

Multicast is performed in a packet-based network switch having a switch fabric of store-and-forward switch nodes. Congestion and blocking at an ingress port is avoided because packet replication is performed at random nodes dispersed throughout the switch fabric. Each multicast packet inserted into the switch fabric by the ingress port is sent to a randomly-selected node. The random node replicates the multicast packet into many unicast packets that are routed to egress ports. A SONET frame can be divided into several multicast packets that are dispersed to different random nodes before replication, thus dispersing congestion. Replication can be delayed until the next SONET frame to prevent latency build up from propagation delays in the switch fabric. Alternately, the SONET payload envelope pointer can be advanced by the propagation delay. Lookup tables at the random nodes can include a list of destinations so that all the destination addresses do not have to be stored in each multicast packet header.

Claims

1. A mesh-based packet switch with multicast capability comprising:

a plurality of ingress ports for receiving data and generating packets including multicast packets;

a plurality of egress ports for transmitting data from the packet switch;

a switch fabric having a plurality of switching nodes each for storing and forwarding packets within the switch fabric, the switching nodes including input nodes coupled to ingress ports in the plurality of ingress ports and output nodes coupled to egress ports in the plurality of egress ports;

wherein an ingress port injecting a multicast packet generates a multicast header to attach to the multicast packet, the multicast header including;

a multicast flag indicating that the multicast packet is a packet being sent to many egress ports;

a random field for storing an address of a random node within the switch fabric; and

a multicast destination identifier for indicating which egress ports to send the multicast packet to;

wherein the multicast packet is initially routed to the random node before packet replication;

wherein the random node stores the multicast packet sent from the ingress port, the random node replicating the multicast packet to generate a plurality of unicast packets, the unicast packets each having a header including;

a destination field for storing a destination address of an output node coupled to an egress port identified by the multicast destination identifier of the multicast packet received by the random node;

wherein the switching nodes route the unicast packets from the random node to the output nodes identified by the destination fields of the unicast packets generated by the random node;

wherein the random node is selected at random from all the switching nodes in the switch fabric,

whereby multicast packets are initially dispersed to randomly-selected nodes within the switch fabric before packet replication and whereby congestion at the input node is reduced by replicating the multicast packet at the random node.

2. The mesh-based packet switch of claim 1 wherein the multicast destination identifier comprises a list of the destination addresses.

3. The mesh-based packet switch of claim 1 wherein the random node further comprises:

a lookup table, indexed by the multicast destination identifier from the multicast packet, for storing the destination addresses written to the headers of the unicast packets generated by the random node,

whereby destination addresses for the multicast packet from the ingress port are locally stored at the random node.

4. The mesh-based packet switch of claim 3 wherein the lookup table further stores second-level multicast identifiers, the second-level multicast identifiers for indexing the lookup table to locate a second group of destination addresses;

wherein the random node further generates a second multicast packet with a second multicast header that includes a second random field storing an address of a second random node within the switch fabric, the second multicast header storing a second-level multicast identifier from the lookup table;

wherein the second multicast packet is routed from the random node to the second random node by switching nodes in the switch fabric;

wherein the second random node replicates the second multicast packet to generate unicast packets, the unicast packets each having a header including a destination field read from a second lookup table at the second random node,

whereby nested packet replication occurs at two random nodes.

5. The mesh-based packet switch of claim 4 wherein data received by the ingress port is arranged in a Synchronous Optical NETwork (SONET) frame;

wherein packet replication by the random node and by the second random node is synchronized to the SONET frame.

6. The mesh-based packet switch of claim 1 wherein the address of a random node within the switch fabric is randomly generated by a dispersion function to select as the random node any switching node from any set of switching nodes in the switch fabric, including switching nodes that are not on a route to the output node;

wherein the dispersion function is random with respect to the output node, wherein the random node is selected by the dispersion function selected from the group consisting of a pseudo-random selector, a true-random selector, and a round-robin cycler,

whereby packets are first routed to a random node and replicated at the random node before being routed to their output node.

7. The mesh-based packet switch of claim 6 wherein the switch fabric is an isotropic mesh.

8. The mesh-based packet switch of claim 6 wherein data received by the ingress port is arranged in a Synchronous Optical NETwork (SONET) frame;

wherein the ingress port also injects a serial multicast packet into the switch fabric, the serial multicast packet having a serial header attached to the serial multicast packet by the ingress port, the serial header including;

a multicast flag indicating that the multicast packet is a packet being sent to many egress ports; and

a multicast destination identifier for indicating which egress ports to send the multicast packet to;

wherein the serial multicast packet is routed by the switching nodes to a first egress port indicated by the multicast destination identifier;

wherein the first egress port replicates and outputs data from within the serial multicast packet;

wherein the first egress port sends the serial multicast packet to a second egress port indicated by the multicast destination identifier;

wherein the second egress port replicates and outputs data from within the serial multicast packet;

wherein the second egress port sends the serial multicast packet to a third egress port indicated by the multicast destination identifier;

wherein the third egress port replicates and outputs data from within the serial multicast packet,

whereby serial multicast packets are routed to a chain of egress ports for replication at the egress ports.

9. The mesh-based packet switch of claim 8 wherein each egress port indicated by the multicast destination identifier re-injects the serial multicast packet into the switch fabric after a start of a next SONET frame,

wherein a latency of one SONET frame period is added for each egress port that re-injects the serial multicast packet into the switch fabric,

whereby latency build-up within a SONET frame is eliminated.

10. The mesh-based packet switch of claim 8 wherein each egress port indicated by the multicast destination identifier adjusts a synchronous payload envelope (SPE) pointer by a predetermined fixed amount for data output by that egress port, the SPE pointer for indicating a location of a first data byte within a SONET frame;

wherein each egress port indicated by the multicast destination identifier re-injects the serial multicast packet into the switch fabric;

whereby latency build-up within a SONET frame is eliminated.

11. The mesh-based packet switch of claim 10 wherein the SPE pointer is advanced by a propagation delay for the serial multicast packet through the switch fabric,

whereby the SPE pointer is advanced by a switch-fabric propagation delay.

12. The mesh-based packet switch of claim 8 wherein the serial multicast packet is first sent to the random node prior to being sent to the first egress port, and wherein the serial multicast packet is sent from the first egress port to a second random node prior to being sent to the second egress port,

whereby the serial multicast packet is routed through random nodes.

13. A multicasting packet switch comprising:

a switch fabric containing a plurality of switch node means each for routing packets within the switch fabric;

ingress means, coupled to switch node means in the switch fabric, for receiving and packetizing data from an external source;

egress means, coupled to switch node means in the switch fabric, for receiving packets sent through the switch fabric and for arranging in sequence order packets before transmission to an external destination;

multicast means, coupled to the ingress means, for generating a multicast packet that includes a destination identifier that identifies a series of egress means to receive the multicast packet;

wherein each egress means that receives and re-injects the multicast packet includes;

duplication means, receiving the multicast packet, for duplicating data from the multicast packet for transmission to the external destination;

re-injection means, receiving the multicast packet, for re-injecting the multicast packet into the switch fabric for routing to another of the egress means identified by the destination identifier; and

timing means, coupled to the re-injection means, for re-injecting the multicast packet after a start of a next Synchronous Optical NETwork (SONET) frame,

whereby latency buildup within a SONET frame period is avoided during multicast.

14. The multicasting packet switch of claim 13 further comprising:

parallel multicast means, coupled to the ingress means, for generating a parallel multicast packet that includes a destination identifier that identifies a series of egress means to receive the parallel multicast packet;

scattering means, coupled to the ingress means, for scattering packets in a series of packets to different switch node means within the switch fabric;

wherein each switch node means that receives the parallel multicast packet includes;

replication means, receiving the parallel multicast packet, for duplicating the parallel multicast packet to generate a plurality of unicast packets;

addressing means, coupled to receive the destination identifier from the parallel multicast packet, for generating addresses of egress means identified by the destination identifier and for writing these addresses to destination means in the unicast packets; and

re-injection means, receiving the unicast packet, for re-injecting the unicast packets into the switch fabric for routing to the egress means identified by the destination identifier;

whereby packet replication occurs at switch node means rather than at ingress or egress.

15. The multicasting packet switch of claim 14 wherein the scattering means includes randomizing means for selecting at random from the switch node means in the switch fabric,

whereby multicast packets are randomly scattered within the switch fabric before packet replication.

16. A method for multicasting packets in a mesh-based network comprising:

receiving at an ingress port a data stream for multicasting to a plurality of egress ports;

dividing the data stream into a series of multicast packets;

writing a multicast identifier that identifies the plurality of egress ports in the network to a header for each multicast packet, the multicast packets being sent to each egress port in the plurality of egress ports;

generating an intermediate identifier for an intermediate switch within the network for each multicast packet;

wherein the intermediate identifier is different for each multicast packet in a series of packets;

writing the intermediate identifier for the intermediate switch to the header for each multicast packet;

injecting each multicast packet into the network at a source switch coupled to the ingress port;

routing the multicast packets from the source switch to the intermediate switch identified by the intermediate identifier in the header of each of the multicast packets;

wherein each multicast packet in the series of multicast packets is routed to a different intermediate switch within the network;

at the intermediate switch, replicating the multicast packet to a plurality of replicated packets, the plurality of replicated packets having destinations in the plurality of egress ports identified by the multicast identifier;

routing the plurality of replicated packets from the intermediate switch toward different egress ports in the plurality of express ports; and

re-assembling the data stream from a series of the replicated packets received at each egress port in the plurality of egress ports, each packet in the series of the replicated packets being received from a different intermediate switch;

generating a second multicast packet at the intermediate switch by replicating the multicast packet received from the source switch;

generating a second intermediate identifier for a second intermediate switch;

writing the second intermediate identifier to a header of the second multicast packet

routing the second multicast packets from the intermediate switch to the second intermediate switch identified by the second intermediate identifier in the header of the second multicast packet;

at the second intermediate switch, replicating the second multicast packet to a plurality of second replicated packets, the plurality of second replicated packets having destinations in the plurality of egress ports identified by the multicast identifier;

routing the plurality of second replicated packets from the intermediate switch toward different egress ports in the plurality of egress ports,

wherein the data stream is a Synchronous Optical NETwork (SONET) frame having data arranged into rows;

wherein dividing the data stream into a series of multicast packets comprises forming each row of the SONET frame into a multicast packet;

delaying routing of the second replicated packets until a start of a next SONET frame, whereby latency buildup is avoided by synchronizing multicast packet replication to SONET frame timing.

17. The method of claim 16 further comprising:

using the multicast identifier to locate a matching entry in a lookup table at the intermediate switch;

reading destination addresses from the matching entry in the lookup table;

writing the destination addresses to headers of the replicated packets;

routing the replicated packets to egress ports identified by the destination addresses in the headers read from the lookup table at the intermediate switch,

whereby destination addresses of egress ports are read from the lookup table at the intermediate switch.