System and method for multipoint-to-multipoint multicasting

• US 6,353,596 B1
• Filed: 04/12/1996
• Issued: 03/05/2002
• Est. Priority Date: 04/12/1996
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Ramakrishnan, Kadangode K., Grossglauser, Matthias
• Primary Examiner(s): MARCELO, MELVIN C
• Application Number:
  US08/631,869
• Time in Patent Office: 2,153 Days
• Field of Search: 340/256, 340/260, 340/390, 340/408, 340/409
• US Class Current: 370/256
• CPC Class Codes: H04L 12/185 with management of multicast group membership

Abstract

A system and method are provided for a scalable and efficient multipoint-to-multipoint multicast in packet and sub-packet based communications networks. The methodology of the invention incorporates an additional switching feature called cut-through forwarding, which enables the mapping of several incoming virtual channels into one or several outgoing virtual channels. The inventive methodology further provides a shared tree spanning all senders and receivers of the multicast group. Centrally initiated group setup as well as dynamic group membership changes are incorporated into the invention. An additional feature of the invention, designated “short-cutting”, allows for the transmission of a packet to follow the shortest path along the shared tree. A methodology is also provided for achieving interoperability among switching nodes in a network which are capable of fully implementing the multipoint-to-multipoint multicast method of the invention and other switching nodes which lack that capability.

Claims

1. A cell transfer network which is made up of a plurality of nodes and transmission links interconnecting said nodes, including means for establishing at least one logical connection among a set of said nodes for effecting a transfer of a sequence of said cells from at least one sending node to at least one receiving node, said network including the improvement comprising:

means for responding to a specification of a multipoint-to-multipoint multicast group using said network by specifying a single spanning tree for said multicast group, said spanning tree comprising switching nodes and links in said network connecting sending and receiving nodes in said multicast group, at least one of said switching nodes in said spanning tree established as a core node for said tree;

means for responding to a request by any one of said sending nodes to send at least one sequence of said cells to receiving nodes in said multicast group via logical connections established in said spanning tree; and

means for causing another switching node in said spanning tree to operate on a cell sequence from a sending node in said multicast group transmitted toward said core node so as to cause a copy of said cell sequence to be provided directly to a receiving node in a hierarchy of said spanning tree at or below a location in said hierarchy of said another switching node.

2. The improved cell transfer network of claim 1 wherein said means for establishing at least one logical connection operates to establish at most one logical connection per link of said spanning tree.

3. The improved cell transfer network of claim 1 wherein said means for establishing at least one logical connection operates to establish a common logical connection for all links in said spanning tree.

4. The improved cell transfer network of claim 1, claim 2 or claim 3, wherein a switching node in said spanning tree receives input cell sequences from a multiple of said sending nodes in said multicast group, further including means for causing said switching node to completely process a cell sequence received from a first input path prior to processing any portion of another cell sequence received from another of said multiple input paths.

5. The improved cell transfer network of claim 1, claim 2 or claim 3, further including means for causing at least one of said switching nodes in said spanning tree to maintain a marker at respective ports of said at least one switching node for each of said respective ports serving a receiving node of said multicast group downstream in said spanning tree from said respective port.

6. A method employed in a cell transfer network having a plurality of nodes and links to add an additional sending/receiving node to a set of nodes which belong to a multipoint-to-multipoint multicast group,

the method having the steps of:

sending a message via a spanning tree in said network associated with said multicast group from said additional sending/receiving node toward a core node of said multicast group indicating that said additional node is to be added to said multicast group; and

adding said additional node and any nodes traversed by said message which are not already in said spanning tree to said spanning tree.

7. The cell transfer network method of claim 6 including the additional step of causing at least one of said nodes traversed by said message to maintain a marker at respective ports of said at least one node for each of said respective ports serving a receiving node of said multicast group downstream in said spanning tree from said respective port.

8. The cell transfer network method of claim 7 including the further step of causing at least one of said nodes traversed by said message to operate on a sequence of said cells received at an input port of said at least one node from a sending node in said multicast group so as to cause a copy of said cell sequence to be transferred to an output port connected to a receiving node in said multicast group located downstream in said spanning tree.

9. A method for multipoint-to-multipoint routing of communications traffic among a plurality of information sources and information sinks connected to a communications network, said network being comprised of interconnected switching nodes and transmission links defining transmission paths in said network, wherein said communications network is arranged to transmit information within said network in the form of discrete units, said methodology comprising the steps of:

specifying a unique identifier for association with each of a set of said information sources and information sinks, said set of sources and sinks constituting a multicast group;

selecting at least one switching node in said network to act as an anchor for signalling messages sent toward said anchor from sources/sinks constituting said multicast group, said anchor and a set of paths for said signalling messages constituting a spanning tree for said multicast group;

providing communications paths in said spanning tree, for transmission of information among members of said multicast group; and

where a switching node in said spanning tree includes multiple input paths, from a multiple of said sources in said multicast group, causing said switching node to completely process an information segment of predefined size received from a first input path prior to processing any portion of another information segment received from another of said multiple input paths.

10. The method for routing multipoint-to-multipoint communications traffic of claim 9 including an additional step of causing a switching node in said spanning tree to operate on an information unit from an information source in said multicast group transmitted toward said anchor, so as to cause a copy of said information unit to be provided directly to an information sink in a hierarchy of said spanning tree at or below a location in said hierarchy of said switching node.

11. The method for routing multipoint-to-multipoint communications traffic of claim 9 wherein said unique identifier includes an address for said anchor and at least one other identification parameter.

12. The method for routing multipoint-to-multipoint communications traffic of claim 9 wherein said communications paths in said spanning tree establish a shortest path within said network between each of said sources/sinks and said anchor.

13. The method for routing multipoint-to-multipoint communications traffic of claim 9 wherein said communications paths in said spanning tree establish a least-cost routing within said spanning tree.

14. The method for routing multipoint-to-multipoint communications traffic of claim 9, wherein a last portion of each said predefined segment is identified by an end-of-segment marker and said switching node operates to recognize said end-of-segment marker prior to accepting for processing information from said another input path.

15. The method for routing multipoint-to-multipoint communications traffic of claim 9 wherein said communications paths in said spanning tree are constituted as not more than one logical connection per link.

16. The method for routing multipoint-to-multipoint communications traffic of claim 9 wherein all of said communications paths in said spanning tree are associated with a common logical connection.

17. The method for routing multipoint-to-multipoint communications traffic of claim 9 wherein said communications network operates in accordance with a networking protocol known as Asynchronous Transfer Mode (“

ATM”

) and wherein said units for transmission of information within said network are established as cells, as defined by said ATM protocol.

18. The method for routing multipoint-to-multipoint communications traffic of claim 17 wherein said predefined information segment operated on by said step of causing each said switching node in said tree to completely process said predefined segment is constituted as a grouping of said ATM cells.

19. The method for routing multipoint-to-multipoint communications traffic of claim 18, wherein a last cell in each said grouping of ATM cells is identified by an end-of-segment marker and said switching node operates to recognize said end-of-segment marker prior to accepting for processing information from said another input path.

20. The method for routing multipoint-to-multipoint communications traffic of claim 19 wherein said grouping of ATM cells is constructed in accordance with an adaptation layer protocol designated as AAL5, and further wherein said end-of-segment marker is as defined by said AAL5 protocol.

21. The method for routing multipoint-to-multipoint communications traffic of claim 9 wherein membership of said information sources and said information sinks in said multicast group may be dynamically adjusted.

22. The method for routing multipoint-to-multipoint communications traffic of claim 21, wherein said dynamic membership changes occur in response to a request from a source/sink for a join to or leave from said membership.

23. The method for routing multipoint-to-multipoint communications traffic of claim 22 wherein said membership changes occur without notification of said change to said anchor.

24. The method for routing multipoint-to-multipoint communications traffic of claim 21, wherein said dynamic membership changes occur in response to a direction from said anchor.

25. The method for routing multipoint-to-multipoint communications traffic of claim 21, wherein said dynamic membership changes occur in response to a request from a third party.

26. The method for routing multipoint-to-multipoint communications traffic of claim 9 including the further step of causing at least one of said switching nodes in said spanning tree to maintain a marker at respective ports of said node for each of said respective ports serving an information sink of said multicast group downstream from said respective port.

27. The method for routing multipoint-to-multipoint communications traffic of claim 26 wherein said switching nodes operate to avoid transmitting information units to portions of said tree connected to ports not having said marker.

28. The method for routing multipoint-to-multipoint communications traffic of claim 9 wherein the step of causing each said switching node to completely process an information segment includes the substep of:

recognizing a port serving one of said multiple input paths having low transmission throughput;

causing information segments arriving at said low transmission throughput port to be buffered until a complete one of said information segments has been received at said port, regardless of when a first portion of said segment is received at said port relative to an arrival time for a segment portion at a port serving another of said multiple input paths.

29. The method for routing multipoint-to-multipoint communications traffic of claim 9 wherein the step of causing each said switching node to completely process an information segment includes the substep of:

establishing a waiting time threshold in respect to a time interval between receipt at an input port of a portion of an information segment and a next portion of said segment, said next portion being inclusive of said final portion having said end-of-segment marker; and

where said time interval exceeds said threshold, causing said switching node to inject a “

dummy”

end-of-segment portion at said input port, thereby causing processing of said information segment to be completed by said switching node and processing of a new information segment to begin.

39. In a communications system for carrying out the multipoint-to-multipoint routing methodology of claim 9 (hereafter, the “

SEAM”

methodology) among a defined multicast group of senders and receivers, wherein said communications system is operated across a communications network comprised of a plurality of switching nodes and interconnecting transmission links, and further wherein said plurality of switching nodes includes a first portion characterized as being operable to fully implement said SEAM methodology (hereafter, “

SEAMable nodes”

) and a remaining portion being incapable of fully implementing said SEAM methodology (hereafter, “

nonSEAMable nodes”

), a method for effecting interoperability between said SEAMable nodes and said nonSEAMable nodes in carrying out said SEAM methodology across said network, said method comprising the steps of;

identifying nonSEAMable nodes in said network and designating each contiguous grouping of one or more of said nonSEAMable nodes as a nonSEAMable island;

identifying SEAMable nodes that directly interface nodes included in each said nonSEAMable island (hereafter designated as “

border SEAMable nodes”

);

establishing, for each of said senders served by a nonSEAMable island node, a point-to-multipoint virtual connection reaching all of said receivers served by nodes in said nonSEAMable island and all border SEAMable nodes interfacing said nonSEAMable island;

establishing, for each of said border SEAMable nodes interfacing said nonSEAMable island, a point-to-multipoint virtual connection to all of said receivers served by nodes in said nonSEAMable island and all remaining of said border SEAMable nodes interfacing said nonSEAMable island;

causing each of said border SEAMable nodes to map all incoming point to multipoint virtual connections from said nonSEAMable island into a SEAM multipoint-to-multipoint virtual connection established for said multicast group on other ports of each said border SEAMable nodes; and

causing each of said border SEAMable nodes to map all outgoing point to multipoint virtual connections to said nonSEAMable island into said SEAM multipoint-to-multipoint virtual connection established for said multicast group on other ports of each said border SEAMable nodes.

40. The method for effecting interoperability between SEAMable nodes and nonSEAMable nodes of claim 39 including the further steps of:

causing a first marker to be maintained at said border SEAMable nodes when at least one sender of said multicast group is served by a port of said border SEAMable node other than a port serving said nonSEAMable island;

causing a second marker to be maintained at respective ports of said border SEAMable nodes serving said multicast group for each of said respective ports having at least one receiver of said multicast group downstream from said respective port;

for said point-to-multipoint virtual connections established for said senders served by said nonSEAMable island nodes, eliminating any of said border SEAMable nodes interfacing said nonSEAMable island as destinations for said point-to-multipoint virtual connections where at least one port of said border SEAMable node other than a port interfacing said nonSEAMable island does not exhibit said second marker; and

for said point-to-multipoint virtual connections established from said border SEAMable nodes to said nonSEAMable island, eliminating any of said border SEAMable nodes not exhibiting said first marker as roots for said point-to-multipoint connection.

41. The method for effecting interoperability between SEAMable nodes and nonSEAMable nodes of claim 40 including the further step of:

for respective ones of said border SEAMable nodes interfacing said nonSEAMable island serving as roots for said point-to-multipoint virtual connections, eliminating any of said remaining border SEAMable nodes as destinations for said point-to-multipoint virtual connections where at least one port for respective ones of said remaining border SEAMable nodes, other than a port interfacing said nonSEAMable island, does not exhibit said second marker.

30. In a communications network comprised of interconnected switching nodes and transmission links defining transmission paths therein, wherein said communications network is arranged to transmit information within said network in the form of discrete units, an improvement in said network for enabling multipoint-to-multipoint multicast routing of communications traffic among a plurality of information sources and information sinks connected to said network, said improvement comprising:

means for causing a unique identifier to be associatiated with a set of information sources and information sinks comprising a multicast group;

means for selecting at least one switching node in said network to act as an anchor for signalling messages sent toward said anchor from said set of sources/sinks in said multicast group, said anchor and a set of paths for said signalling messages constituting a spanning tree for said multicast group;

means for providing communications paths in said spanning tree, for transmission of information among members of said multicast group; and

where a switching node in said spanning tree includes multiple input paths, from a multiple of said sources in said multicast group, means for causing said switching node to completely process an information segment of predefined size received from a first input path prior to processing any portion of another information segment received from another of said multiple input paths.

31. The improved network for routing of multipoint-to-multipoint communications traffic of claim 30 further including means for causing a switching node in said spanning tree to operate on an information unit from an information source in said multicast group transmitted toward said anchor, so as to cause a copy of said information unit to be provided directly to an information sink in a hierarchy of said spanning tree at or below a location in said hierarchy of said switching node.

32. The improved network for routing of multipoint-to-multipoint communications traffic of claim 30 wherein said unique identifier includes an address for said anchor and at least one other identification parameter.

33. The improved network for routing of multipoint-to-multipoint communications traffic of claim 30, further including means for recognizing an end-of-segment marker included in a last portion of each said predefined segment, prior to accepting for processing information from said another input path.

34. The improved network for routing of multipoint-to-multipoint communications traffic of claim 30 wherein said communications network operates in accordance with a networking protocol known as Asynchronous Transfer Mode (“

ATM”

) and wherein said units for transmission of information within said network are established as cells, as defined by said ATM protocol.

35. The improved network for routing of multipoint-to-multipoint communications traffic of claim 30 further including means for causing at least one of said switching nodes in said spanning tree to maintain a marker at respective ports of said node for each of said respective ports serving an information sink of said multicast group downstream from said respective port.

36. The improved network for routing of multipoint-to-multipoint communications traffic of claim 35 where said switching nodes operate to avoid transmitting information units to portions of said tree connected to ports not having said marker.

37. The improved network for routing of multipoint-to-multipoint communications traffic of claim 30 wherein said means for causing each said switching node to completely process an information segment further includes:

means for recognizing a port serving one of said multiple input paths having low transmission throughput; and

means for causing information segments arriving at said low transmission throughput port to be buffered until a complete one of said information segments has been received at said port, regardless of when a first portion of said segment is received at said port relative to an arrival time for a segment portion at a port serving another of said multiple input paths.

38. The improved network for routing of multipoint-to-multipoint communications traffic of claim 33 wherein said means for causing each said switching node to completely process an information segment further includes:

a waiting time threshold in respect to a time interval between receipt at an input port of a portion of an information segment and a next portion of said segment, said next portion being inclusive of said final portion having said end-of-segment marker; and

where said time interval exceeds said threshold, means for causing said switching node to inject a “

dummy”

end-of-segment portion at said input port, thereby causing processing of said information segment to be completed by said switching node and processing of a new information segment to begin.