Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
1996-04-12
2002-03-05
Marcelo, Melvin (Department: 2663)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S390000, C370S409000
Reexamination Certificate
active
06353596
ABSTRACT:
FIELD OF THE INVENTION
This application is related to multicasting in communications networks and more particularly to an improved method for providing multipoint-to-multipoint multicasting in sub-packet switched communications networks.
BACKGROUND OF THE INVENTION
Point-to-point communication across a communications network among a single sender and a single receiver is well known and networking protocols for point-to-point communications services are well established. Increasingly, however, a communications arrangement needs to be established among multiple senders and/or multiple receivers constituting a group having some community of interest. Accordingly, the concept of a group multicast service has evolved for enabling multiple senders to communicate to multiple receivers. It is known in the art to provide a point to multipoint connection. However, there is no present methodology for efficiently providing a multicast service between multiple senders and multiple receivers.
Networking applications can benefit in terms of scalability, performance and design simplicity from a group multicast service, i.e., a service enabling multiple senders to communicate to multiple receivers. Examples of multicasting on a broad scale include human collaboration such as video-conferencing and shared workspaces. Additionally, many applications in Local Area Networks (LANs) have often taken multicasting for granted (e.g., for address resolution, resource discovery, etc.). Moreover, it is believed that the need for multicasting will become even more pressing with the wide-scale deployment of distributed systems (e.g., maintaining replicated databases).
A number of approaches have been suggested for implementation of a multipointto-multipoint multicasting service in a communications network. In the Internet Protocol (IP) environment, two noteworthy approaches are the Core Based Tree (“CBT”) approach and the Protocol Independent Multicast (“PIM”) approach. The basic idea of CBT [see, T. Ballardie, P. Francis, and J. Crowcroft, “Core Based Trees (CBT)” in
Proc. ACM SIGCOMM
93, (San Francisco, Calif.), September 1993] is to have a single tree per group, rooted at a core router. This tree is shared between all the senders to the group. A multicast group is set up by first choosing one (or several) core routers, and making them known to potential receivers. Receivers can then join the multicast group by sending join messages towards the core. As soon as the join message either reaches the core or a router that is part of the requested group's tree, the new receiver is attached to the tree. Senders simply unicast packets to the core. The core then forwards packets to the receivers in the group by “multicasting” the packet on the tree.
Two problems are associated with CBT. First, the reliability of the entire group is tied to the reliability of the core. If the core fails, the entire group fails. Second, the price paid by having a single tree shared by all senders sending to this group are traffic concentration and possibly increased delays as compared to having multiple sender-based shortest path trees. Moreover, the core may be a bottleneck, which contributes to the delays as a result of queuing.
PIM [see, S. Deering, et al., “An Architecture for Wide-Area Multicast Routing”, in
Proc. ACM SIGCOMM '
94, (London), August 1994] attempts to combine the advantages of CBT with those of sender-based shortest path trees. By default, a multicast group gets set up as a core-based tree. However, a receiver has the option to request getting packets from a given sender on the shortest path, rather than through the core-based tree. The receiver chooses the option so as to minimize the delay, which may be useful in real-time communication. Both CBT and PIM exploit point-to-multipoint capability already present in IP-based packet networks.
As sender-based trees require per-sender state both in the sender-based tree itself and the shared tree (negative-cache entries saying “do not forward packets from sender S out this interface”), a large number of senders can only be supported on the shared tree. Furthermore, the soft-state approach in PIM requires refreshing this state on a regular basis. This traffic also grows with the number of senders that are supported by sender-based trees. The operation of switching a sender from a shared to a sender-based tree is relatively costly and results in a transition period where loss can occur. Finally, joins of new receivers get more costly as the number of senders supported by sender-based trees increases (in the straightforward one-tree-per-sender case, a receiver has to join all of the trees of all of the interesting senders) because the new receiver has to learn of the existence of these senders, which happens by temporarily grafting them back onto the shared tree.
For networks based on the Asynchronous Transfer Mode (ATM) networking protocol, other multicasting approaches have been considered. At a base level, ATM multicasting may be implemented as a mesh of point-to-point virtual circuits—i.e., by establishing individual point-to-point communications paths among all combinations of senders and receivers in such a multicast group. It will be apparent that such an embodiment would be highly resource intensive because each sender/receiver communications path would have to be configured using a separate virtual circuit, likely resulting in performance degradation (including duplicate transmission over the network links) as well as cost penalties. Moreover, it is often the case that virtual circuits are a scarce commodity.
It is also known in the art to implement an ATM point-to-multipoint service, wherein a “tree” is established representing a communications path from a single sender to multiple receivers. In such a tree, the sender can be seen as the root of the tree and each receiver as a branch of the tree. In such a point-to-multipoint service, common communications packets intended for multiple receivers are replicated at the branching point(s), rather than at the root, thus avoiding the need for redundant transmissions to those branching points. However, in order for multiple senders to multicast to a set of receivers, the use of such a point-to-multipoint approach results in multiple trees, all trying to talk to the same set of receivers.
The above limitation on multiple senders multicasting to multiple receivers has been addressed by the use of multicast servers—i.e., the establishment of an infrastructure of point-to-multipoint connections along with a server to achieve multipoint-to-multipoint communication. Specifically a multicast server is established to which all the senders send on distinct point-to-point circuits. The server sequences the information and sends it out on a point-to-multipoint connection to the ultimate receivers. The members of the multicast group form a multicast “cluster” and establish a connection to the multicast server, which itself establishes a point-to-multipoint connection to the receivers.
This approach suffers from the parallel deficiencies of requiring the dedication of a server to each multipoint-to-multipoint connection, and, where sub-packet communications networks are involved, as with ATM, also requiring reassembly of incoming sub-packets at the multicast server, before queuing them to be forwarded on the single point-to-multipoint connection to the receivers. Such a dedicated server represents not only a critical failure point that can take down the entire multicast arrangement, but also introduces significant latency as each arriving packet must be reassembled before being forwarded to the receivers. Moreover, where one or more receivers are located at a branching point between a sender and the server, it is necessary for packets to be forwarded from that sender all the way to the server and then back to the receiver, thus introducing both latency and the overhead of multiple traversal of the same path for such packets.
SUMMARY OF THE INVENTION
A system and method for implementation of multi
Grossglauser Matthias
Ramakrishnan Kadangode K.
LandOfFree
System and method for multipoint-to-multipoint multicasting does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for multipoint-to-multipoint multicasting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for multipoint-to-multipoint multicasting will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2861442