Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-03-13
2004-08-31
Cangialosi, Salvatore (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S401000, C370S408000
Reexamination Certificate
active
06785275
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the global Internet, and more particularly to Internet routing protocols for supporting multicast packet delivery.
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 relatively 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 a 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 can 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 the 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, as described in detail below, claims an innovative multicast routing solution when the latter multicast packet format has been used (e.g., choosing a multicast capable router and placing an IP address into the IP packet destination field and placing all of the multicast destination IP addresses in the OPTIONS field).
SUMMARY OF THE INVENTION
In view of the foregoing and other problems of the conventional methods and structures, an object of the present invention is to provide a method and structure in which a multicast scheme and method are realized that are 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 introduce a scheme where the introduction of a single multicast-capable router will enable the entire network multicast-capable.
A further object of the present invention is to guarantee the optimum multicast routing (e.g., each packet will be delivered from a multicast-capable router to every destination along the shortest path defined in the exiting unicast routing).
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.
A still further object of the present invention is to utilize the existing unicast routing protocols for determining multicasting routes.
Another object of the present invention is to impose no new functional requirement at each multicast destination node by guaranteeing that each destination always receives unicast packets.
Yet 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 of the present invention, a routing table for use with a router in a world-wide network, includes extending an existing routing table to include a “multicast-destination” (MD) column.
In a second aspect, a routing system, includes a routing unit for updating a next-node (NN) column of a routing table and for routing unicast packets by referencing the NN column of the routing table, a packet regeneration unit for referencing a column MD of the routing table and for selectively creating copies of at least one of unicast and multicast packets, and a multicast-destination (MD) discovery unit for updating the MD column of the routing table.
In a third aspect, a method of processing a packet, includes receiving a packet at a router, checking by the router if the packet's destination is itself or not, if the packet's destination is not the router, then the said packet is routed in a traditional manner, and if the received packet's destination is itself and if an entry in a routing table is MC=1 indicating that the packet is a multicast packet, then forwarding the packet to a packet regeneration process.
The present invention, as described in detail below, claims an innovative multicast routing solution when the latter multicast packet format has been used (e.g., choosing a multicast capable router and placing IP address into the IP packet destination field and placing all of the multicast destination IP addresses in the OPTIONS field). The Internet IP packet which support this latter multicast packet format may appear as the following: in addition to other fields of the Internet IP packet, it has a PROTOCOL field indicating that the
Boivie Richard Harold
Maruyama Kiyoshi
Cangialosi Salvatore
Ludwin, Esq. Richard M.
McGinn & Gibb PLLC
LandOfFree
Method and system for creating small group multicast over an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for creating small group multicast over an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for creating small group multicast over an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3299683