Multiplex communications – Channel assignment techniques – Messages addressed to multiple destinations
Reexamination Certificate
2000-03-13
2004-06-29
Cangialosi, Salvatore (Department: 2661)
Multiplex communications
Channel assignment techniques
Messages addressed to multiple destinations
C370S393000, C370S408000
Reexamination Certificate
active
06757294
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a world-wide network (e.g., such as the global Internet), and more particularly to those Internet routing protocols for supporting multicast.
2. Description of the Related Art
The Internet is the world's largest network, and it has become essential to businesses as well as to consumers. The success of Internet is partly due to the simplicity of routing protocols used in the network for packet delivery.
There are basically three types of packets delivery mechanisms including “unicast” that allows the delivery of information from a source to a particular destination, “broadcast” that allows the delivery of information from a source to every destination in the network, and “multicast” that allows the delivery of information from a source to a selected group of destinations in the network.
Today, in the Internet, the multicast is supported by using routers called “Class D” routers. In this scheme, prior to conducting the multicast, necessary resources are reserved at those involved Class D routers. Then, multicast may be started. At the conclusion of the multicast, such reserved resources must be freed so that they become available for other multicasts.
Because of this reservation and resource allocation involvement, this Class D router-based multicast scheme is suitable for supporting long-lasting multicasts (e.g., minutes instead of seconds to minimize the overhead of reservation) that involve large numbers of destinations.
However, because of this reservation and resource allocation involvement, it is not suitable for supporting very large numbers of small group multicasts, due to reservation time and resource consumption at each Class D router to keep track of the state of each multicast.
Moreover, because each Class D router must create entries for each multicast group and this entry occupies a certain space, only a finite number of multicasts may be supported.
A way to support an extremely large number of small multicast groups is to let each packet carry routing destinations and alleviate routers from keeping track of states of individual multicast.
There are basically two distinctive methods to carry destinations for multicast purposes. A first method carries a list of multicast destinations and indicates that the packet is a multicast packet (e.g., namely indicating that a packet is not a unicast packet).
A second method is to carry multicast routing information (e.g., sometimes referred to as “source routing” or “routing tree”) that includes the multicast destinations and indicates that the packet is a multicast packet.
The second approach has many drawbacks. For example, a source node must create a proper routing sub-tree that contains multicast destinations that is computation intensive, a routing tree description becomes a substantial overhead of each multicast packet, and a new multicast-enabled router must perform a fairly complex routing sub-trees regeneration process for every multicast packet received.
Therefore, desirable solutions for small group multicast are based on a multicast packet that carries a list of multicast destinations and simply indicates that the packet is a multicast packet delivery (e.g., this indicator allows a new multicast router to differentiate multicast packets easily from unicast packets).
In this approach, there are two distinctive Internet Protocol (IP) packet formats for small group multicast depending on how the IP destination address field is used for multicasting packets. Both formats have a control field bit (MC) indicating whether or not a given packet is a multicast (MC=1) or unicast (MC=0).
One type of multicast packet format is to place one of a plurality of multicast destination IP addresses into the IP packet destination field and the remainder of multicast destination IP addresses in the OPTIONS field of the IP packet.
Another type of multicast packet format is to choose a multicast-capable router (e.g., the router that supports the new multicast routing protocol) in the network and place its IP address into the IP packet destination field, and place all of the multicast destination IP addresses in the OPTIONS field. Each of these two formats offers a completely different implementation of routing algorithms and each gives pros and cons.
The present invention described in detail below claims an innovative multicast routing solution when the former multicast packet format has been used
SUMMARY OF THE INVENTION
In view of the foregoing and other disadvantages, drawbacks, and problems of the conventional methods and systems, an object of the present invention is to provide a multicast scheme and method that is suitable for simultaneously supporting a very large number of small group multicasts.
Another object of the present invention is to support gradual introduction of the new multicast-capable router(s) into the network without introducing any disruptions to on-going operations.
Yet another object of the present invention is to provide a scheme that improves resource utilization and multicast efficiency as the number of multicast-capable routers are introduced into the network and as the existing unicast routers are upgraded to the new multicast-capable routers.
Still another object of the present invention is to guarantee the delivery of a multicast packet even if there is no multicast-capable router in the network (thus amicable).
A further object of the present invention is to use an existing routing table for multicasting.
Yet another object of the present invention is to keep the functional requirement of the new multicast capable router to absolute minimum.
A still further object of the present invention is to make a new multicast-capable router completely transparent and independent from any existence or nonexistence of any other multicast-capable routers in the network.
Another object of the present invention is to allow simple swapping of the existing unicast routing protocol software with the new multicast-capable routing protocol software.
In a first aspect, a method (and system) of creating a multicast packet by a source node in world-wide network, includes providing each multicast packet with a predetermined indicator indicating the packet is a multicast packet, one of a plurality of multicast destinations being placed in the packet destination field and a list of remaining multicast destinations being provided in the packet header.
In a second aspect of the invention, a method of regenerating and routing packets by a multicast capable router in a world-wide network, includes for each destination, Dp, D
1
through Dk, finding its next-node (NN) from a routing table, judging whether any of the destinations have the same next node (NN) as another destination, and for the destinations judged to have the same next-node (NN), generating a multicast packet.
In a third aspect of the invention, a method of regenerating a packet by a receiving destination node in a world-wide network, includes determining the number of remaining multicast destinations in the received packet, providing a packet with a predetermined indicator indicating the packet is a multicast when the remaining number of multicast destinations is more than one, or indicating the packet is a unicast packet when the remaining number of multicast destinations is one, one of the plurality of multicast destinations being placed in the packet destination field and a list of remaining multicast destinations being provided in the packet header, and forwarding the regenerated packet to the router from which the original packet was received.
Along with the above aspects, a programmable storage device is provided for storing a program of the methods of the present invention.
With the unique and unobvious features of the present invention, a system and method are provided for creating small group multicast network without disrupting the existing unicast network, and yet which provide guaranteed delivery of multicast packet to all destinations even
Cangialosi Salvatore
Ludwin, Esq. Richard M.
McGinn & Gibb PLLC
LandOfFree
System and method for amicable small group multicast in a... 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 amicable small group multicast in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for amicable small group multicast in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3351836