System and method for performing switching in multipoint-to-multipoint multicasting

• US 6,049,546 A
• Filed: 10/15/1996
• Issued: 04/11/2000
• Est. Priority Date: 10/15/1996
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Ramakrishnan, Kadangode K.
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): NGUYEN, STEVEN H D
• Application Number:
  US08/730,424
• Time in Patent Office: 1,274 Days
• Field of Search: 370/390, 370/389, 370/393, 370/394, 370/396, 370/397, 370/398, 370/399, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418, 370/422, 370/429, 370/432, 370/395 , 370/392, 370/381
• US Class Current: 370/412
• CPC Class Codes: H04L 2012/563 Signalling, e.g. protocols, reference model
• CPC Class Codes: H04L 2012/5658 using the AAL5
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/251 Cut-through or wormhole routing
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method for utilizing buffered switches to perform multipoint-to-multipoint multicasting within a telecommunication network. A switching feature known as cut-through forwarding is implemented for output-buffered switches, shared-memory switches and input-buffered switches.

Claims

1. In a communications network comprised of interconnected switching nodes and transmission paths therein, wherein the communications network is arranged to carry discrete segments of information between information sources and information receivers, a unique multicast group identifier being associated with a subset of information sources and information receivers, the subset of information sources and receivers constituting a multicast group, a method for multipoint-to-multipoint multicast routing of information segments at the switching nodes including an output-buffered switch or shared-memory switch using a spanning tree and having a buffer associated with each output port, said method comprising:

(a) routing a set of information segments to an output port buffer, the set of information segments having a plurality of multicast group identifiers, each information segment having a plurality of portions including a terminal portion, each portion having a multicast group identifier from the plurality of multicast group identifiers; and

(b) establishing, at the output port buffer to which the set of information segments having at least two multicast group identifiers are routed, at least two queues, each queue corresponding to an individual multicast group identifier from the plurality of multicast group identifiers.

2. The method of claim 1, further comprising the step of:

(c) forwarding all portions of a first information segment from the set of information segment and having a first multicast group identifier from the plurality of multicast group identifiers prior to forwarding any portion of another information segment having the first multicast group identifier;

said forwarding step (c) is performed without coordination among output ports.

3. The method of claim 1, further comprising the step of:

(c) inserting a terminal portion of an information segment after a time-out period unique for the output port when an originally transmitted terminal portion of the information segment has been identified as not received.

4. The method of claim 1, wherein said establishing step (b) further comprises the substeps of:

(i) marking each information segment portion from the set of information segments with an input port identifier indicating the input port from which the information segment portion originated; and

(ii) linking together portions of an information segment from the set of information segments having the same input port identifier.

5. The method of claim 1, wherein said establishing step (b) establishes a queue at the output port for each input port from which an information segment portion from the set of information segments was routed for each multicast group identifier from the plurality of information segments.

6. The method of claim 1, wherein the communication network operates in accordance with a networking protocol known as Asynchronous Transfer Mode ("ATM") and wherein the information segments from the set of information segments are established as packets and the information segment portions are packet cells, as defined by the ATM protocol.

7. In a communications network comprised of interconnected switching nodes and transmission links defining transmission paths therein, wherein the communications network is arranged to carry discrete segments of information between information sources and information receivers, a unique multicast group identifier being associated with a subset of information sources and information receivers, the subset of information sources and receivers constituting a multicast group, a buffered switch for multipoint-to-multipoint multicast routing of information segments at the switching nodes, said buffered switch including an output-buffered switch or shared-memory switch using a spanning tree, said buffered switch comprising:

a plurality of input ports interconnected to a plurality of output ports;

a plurality of buffers, each buffer being uniquely associated with one of said plurality of output ports, a set of information segments being routed to an output port buffer from the plurality of output port buffers, the set of information segments having a plurality of multicast group identifiers, each information segment having a plurality of portions including a terminal portion, each portion having a multicast group identifier from the plurality of multicast group identifiers,

the output port buffer to which the set of information segments having at least two multicast group identifiers are routed establishing at least two queues, each queue corresponding to an individual multicast group identifier from the plurality of multicast group identifiers.

8. The buffered switch of claim 7, further comprising:

a plurality of controllers, each controller being connected between one of said plurality of buffers and one of said plurality of output ports, each controller forwarding all portions of a first information segment from the set of information segments and having a first multicast group identifier from the plurality of multicast group identifiers prior to forwarding any portion of another information segment having the first multicast group identifier and forwarding without coordination among controllers.

9. The buffered switch of claim 8, wherein each controller inserts a terminal portion of an information segment after a time-out period unique for the connected output port when an originally transmitted terminal portion of the information segment has been identified as not received.

10. The buffered switch of claim 7, wherein the output buffer marks each information segment portion from the set of information segment with an input port identifier indicating one of said plurality of input ports from which the information segment portion originated, the output buffer links together portions of an information segment having the same input port identifier.

11. The buffered switch of claim 7, wherein the output buffer establishes a queue for each of said plurality of input ports from which an information segment portion from the set of information segments was routed for each multicast group identifier from the plurality of information segments.

12. The buffered switch of claim 7, wherein the communication network operates in accordance with a networking protocol known as Asynchronous Transfer Mode ("ATM") and wherein the information segments from the set of information segments are established as packets and the information segment portions are packet cells, as defined by the ATM protocol.

13. In a communications network comprised of interconnected switching nodes and transmission links defining transmission paths therein, wherein the communications network is arranged to carry discrete segments of information between information sources and information receivers, a unique multicast group identifier being associated with a subset of information sources and information receivers, the subset of information sources and receivers constituting a multicast group, a method for multipoint-to-multipoint multicast routing of information segments at the switching nodes including an input-buffered switch having a buffer associated with each input port, said method comprising:

(a) receiving a set of information segments at an input port buffer, the set of information segments having a plurality of multicast group identifiers, each information segment having a plurality of portions including a terminal portion, each portion having a multicast group identifier from the plurality of multicast group identifiers; and

(b) establishing, at the input port buffer at which the set of information segments having at least two multicast group identifiers are received, at least two queues, each queue corresponding to an individual multicast group identifier from the plurality of multicast group identifiers.

14. The method of claim 13, further comprising the step of:

(c) forwarding all portions of a first information segment from the set of information segment having a first multicast group identifier from the plurality of multicast group identifiers prior to forwarding any portion of another information segment having the first multicast group identifier.

15. The method of claim 13, further comprising the step of:

(c) inserting a terminal portion of an information segment after a time-out period for the input port when an originally transmitted terminal portion of the information segment has been identified as not received.

16. The method of claim 14, wherein said forwarding step (c) resolves contention in forwarding a first information segment from the set of information segments buffered at a first input port to an output port and in forwarding a second information segment from the set of information segments buffered at second input port to the output port.

17. The method of claim 16, wherein said forwarding step (c) resolves contention by a numerical round robin selection of the input ports.

18. The method of claim 16, wherein said forwarding step (c) resolves contention by a random selection of the input ports.

19. The method of claim 13, wherein the communication network operates in accordance with a networking protocol known as Asynchronous Transfer Mode ("ATM") and wherein the information segments from the set of information segments are established as packets and the information segment portions are packet cells, as defined by the ATM protocol.

20. In a communications network comprised of interconnected switching nodes and transmission links defining transmission paths therein, wherein the communications network is arranged to carry discrete segments of information between information sources and information receivers, a unique multicast group identifier being associated with a subset of information sources and information receivers, the subset of information sources and receivers constituting a multicast group, an input-buffered switch for multipoint-to-multipoint multicast routing of information segments at the switching nodes, comprising:

a plurality of input ports interconnected to a plurality of output ports;

a plurality of buffers, each buffer being uniquely associated with one of said plurality of input ports, a set of information segments being received at an input port buffer from the plurality of input port buffers, the set of information segments having a plurality of multicast group identifiers, each information segment having a plurality of portions including a terminal portion, each portion having a multicast group identifier from the plurality of multicast group identifiers,

the input port buffer at which the set of information segments having at least two multicast group identifiers are received establishing at least two queues, each queue corresponding to an individual multicast group identifier from the plurality of multicast group identifiers.

21. The input-buffered switch of claim 20, further comprising:

a plurality of controllers, each controller being connected between one of said plurality of buffers and said plurality of output ports, each controller forwarding all portions of a first information segment from the set of information segments having a first multicast group identifier from the plurality of multicast group identifiers prior to forwarding any portion of another information segment having the first multicast group identifier.

22. The input-buffered switch of claim 21, wherein each controller inserts a terminal portion of an information segment from the set of information segments after a time-out period for the connected input port when an originally transmitted terminal portion of the information segment has been identified as not received.

23. The input-buffered switch of claim 21, wherein each controller resolves contention in forwarding a first information segment from the set of information segments buffered at the input port to an output port from the plurality of output ports and in forwarding a second information segment from the set of information segments buffered at a second input port from the plurality of input ports to the output port.

24. The input-buffered switch of claim 23, wherein each controller resolves contention by a numerical round robin selection of the input ports.

25. The input-buffered switch of claim 23, wherein each controller resolves contention by a random selection of the input ports.

26. The input-buffered switch of claim 20, wherein the communication network operates in accordance with a networking protocol known as Asynchronous Transfer Mode ("ATM") and wherein the information segments from the set of information segments are established as packets and the information segment portions are packet cells, as defined by the ATM protocol.

27. A method for multipoint-to-multipoint multicast routing of information packets at a switching node having a buffer associated with each output port, said method comprising:

performing, at an output port buffer to which a set of information packets having a plurality of multicast group identifiers are routed, the following;

(a) establishing at least two queues at the output port buffer, each queue corresponding to an individual multicast group identifier from the plurality of multicast group identifiers, each information packet having a plurality of cells including a terminal cell, each cell having a multicast group identifier from the plurality of multicast group identifiers; and

(b) buffering each cell from the set of information packets in the queue corresponding to the multicast group identifier from the plurality of multicast group identifiers associated with that cell.

28. A method for multipoint-to-multipoint multicast routing of information packets at a switching node having a buffer associated with each output port, said method comprising:

(a) performing, at an output port buffer to which a set of information packets having a plurality of multicast group identifiers are routed, the following;

i) establishing at least two queues at the output port buffer each queue corresponding to an individual multicast group identifier from the plurality of multicast group identifiers, each information packet having a plurality of cells including a terminal cell, each cell having a multicast group identifier from the plurality of multicast group identifiers;

ii) buffering each cell from the plurality of information packets in the queue corresponding to the multicast group identifier from the plurality of multicast group identifiers associated with that cell; and

b) forwarding all portions of a first information packet from the set of information packets having a first multicast group identifier from the plurality of multicast group identifiers prior to forwarding any portion of another information packet having the first multicast group identifier;

said forwarding step (c) being performed without coordination among output ports.

29. A buffered switch, comprising:

a plurality of input ports interconnected to a plurality of output ports; and

a plurality of buffers, each buffer being uniquely associate with one of said plurality of output ports, a set of information packets being routed to an output port buffer from the plurality of output port buffers, the set of information packets having a plurality of multicast group identifiers, each information packet having a plurality of cells including a terminal cell, each cell having a multicast group identifier from the plurality of multicast group identifiers,

the output port buffer to which information segments having at least two multicast group identifiers are routed establishing at least two queues, each queue corresponding to an individual multicast group identifier from the plurality of multicast group identifiers.

30. A buffered switch, comprising:

a plurality of input ports interconnected to a plurality of output ports;

a plurality of buffers, each buffer being uniquely associated with one of said plurality of output ports, a set of information packets being routed to an output port buffer from the plurality of output port buffers, the set of information packets having a plurality of multicast group identifiers, each information packet having a plurality of cells including a terminal cell, each cell having a multicast group identifier from the plurality of multicast group identifiers,

the output port buffer to which the set of information packets having at least two multicast group identifiers are routed establishing at least two queues, each queue corresponding to an individual multicast group identifier from the plurality of multicast group identifiers; and

a plurality of controllers, each controller being connected between one of said plurality of buffers and its associated output port, each controller forwarding all portions of a first information packet from the set of information packets having a first multicast group identifier from the plurality of multicast group identifiers prior to forwarding any portion of another information packet having the first multicast group identifier and forwarding without coordination among controllers.

31. A method for multipoint-to-multipoint multicast routing of information packets at an input-buffered switch having a buffer associated with each input port, said method comprising:

performing, at an input port buffer to which a set of information packets having a plurality of multicast group identifiers are received, the following;

(a) establishing at least two queues at the input port buffer, each queue corresponding to an individual multicast group identifier from the plurality of multicast group identifiers, each information packet having a plurality of cells including a terminal cell, each cell having a multicast group identifier from the plurality of multicast group identifiers; and

(b) buffering each cell from the set of information packets in the queue corresponding to the multicast group identifier from the plurality of multicast group identifiers associated with that cell.

32. An input-buffered switch for multipoint-to-multipoint multicast routing of information packets, comprising:

a plurality of input ports interconnected to a plurality of output ports;

a plurality of buffers, each buffer being uniquely associated with one of said plurality of input ports, a set of information packets being received at an input port buffer from the plurality of input port buffers, the set of information packets having a plurality of multicast group identifiers, each information packet having a plurality of cells including a terminal cell, each cell having a multicast group identifier from the plurality of multicast group identifiers,

the input port buffer at which the set of information packets having at least two multicast group identifiers are received establishing at least two queues, each queue corresponding to an individual multicast group identifier from the plurality of multicast group identifiers associated with the cell.