Multiplex communications – Pathfinding or routing – Store and forward
Reexamination Certificate
1999-07-07
2002-02-12
Vu, Huy D. (Department: 2664)
Multiplex communications
Pathfinding or routing
Store and forward
C370S392000
Reexamination Certificate
active
06347090
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method to forward a multicast packet in a connectionless multicast system according to claim
1
and to an ingress node and a router realizing such a method according to claim
7
and to claim
8
, respectively, and to an internet network including such an ingress node or such a router according to claim
10
.
Such a method is already known in the art, e.g. from the Article ‘Datagrom Routing for Internet Multicasting’ written by Lorenzo Aguilar, SRI International , Menlo Park Calif., and published in the proceedings of
Sigcomm
84 in March 1984, ACM 0-8791-136-9/84/006/0058 page 58 to 62.
Therein a solution to the problem of multidestination routing in internetworks is described. More particular, at page 59, third paragraph, the so called ‘multidestination addressing’ is described. Such an algorithm places all its destination addresses in an Internet Packet. During propagation, the packet is replicated at gateways, called hereafter routers, and the address list is partitioned among the newly created packets, according their next internet stop. In this way, at each router the next hop for each destination is determined and per next hop a new header is constructed that contains only these destinations for which that next hop is on the shortest path to these destinations. This approach is called in the claims connectionless multicast system.
A problem outstanding with such a connectionless multicast system is however that the forwarding process in the different routers requires, a number of times, the consultation of the unicast routing table whereby this look-up and the re-construction of the packet headers consumes too much processing time. Hereby the wire-speed forwarding can not be achieved.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a method to forward a multicast packet in a connectionless multicast system from an ingress node via a router to a plurality of destinations that does not have the above problem of consuming too much processing for the number of look-ups to the unicast routing table and the re-construction of the packet headers.
According to the present invention this object is achieved with the method of claim
1
which is realized by the ingress node and the router of claim
7
and claim
8
, respectively and by the internet network that includes such an ingress node and such a router of claim
10
.
Indeed, the object is achieved due to the fact that the method, according to claim
1
, comprises the steps:
a) storing by the router in a memory a relation between a value of a receiver update notification and a predefined construction set. The predefined construction set includes a set of next hops that includes one or more next hops. The next hops are determined for each destination of a predefined set of destinations. The next hops are determined according to look-ups to local unicast routing information. The predefined set of destinations e.g. the destinations received within the header of a multicast packet includes only these destinations of the plurality of destinations for which the router is on a path to these destinations.
b) associating by the ingress node to a starting destination set the value of the receiver update notification. Such a starting destination set includes each one of the plurality of destinations. The ingress node furthermore includes this value of the receiver update notification in the multicast packet in order to be forwarded together with the multicast packet; and
c) by the router, upon reception of the multicast packet that includes the value of the receiver update notification, determining a predefined subset of destinations; and determining for the predefined subset of destinations a next hop of the set of next hops according to the value of the receiver update notification and according to the relation to the predefined construction set; and including in the multicast packet the predefined subset of destinations and the value of the receiver update number; and forwarding the multicast packet towards the next hop, the predefined subset of destinations includes these destinations of the plurality of destinations for which the next hop is on a path to these destinations.
Indeed, in this way the ingress node puts the value of the receiver update notification in e.g. the destination address and uses this same number for the following multicast packets whereby a router according to the present invention forwards the multicast packets according to the associated construction set in its memory. Each time the set of destinations changes, the ingress node indicates this to the downstream routers by updating and using a new value for the receiver update notification whereby the router is flagged to adapt the construction set by consulting, only then, the unicast routing table.
It has to be remarked here that the use of a value of the receiver update number is not necessary in order to forward a multicast packet. Indeed, once a value has been defined by the ingress node and has been forwarded to the routers, the value might be used to improve the forwarding process of the routers but is not essential to forward the multicast packets towards the different destinations.
A further remark is that as well traditional routers and routers according to the present invention might be used simultaneous in the network. Indeed, in the event of a traditional router that not works with a memory for storing the relations between receiver update notification and construction set, the router is still able to forward the multicast packets according to the prior art connectionless multicast procedures. Such a router just ignores the inclusion of such a receiver update notification in the multicast packet. On the other hand, a router according to the present invention will use the presence of a value for the receiver update notification and is enabled to improve its forwarding process.
Furthermore, it has to be remarked that the expression ‘is on a path to these destinations’ is used in the application to mention the route from the ingress node to the destinations. Hereby it has to be understood that usual a shortest path is used for the routing of the multicast packets from the ingress node to the destinations. However the use of another predefined path from the ingress node to the different destinations that depends upon other kinds of criteria e.g. delay and bandwidth in order to be determined is not excluded by the present invention.
It has to be remarked that a clear difference arises between a receiver update notification and a multicast group number. Indeed, the receiver update notification is a reference to a construction set that includes information from the unicast routing tables but that is not essential to be used to forward the multicast packets. Whereas a multicast group number is a reference to information in a multicast routing table that is essential to be looked up in order to forward the multicast packets.
A further remark is that it has to be understood that the expression ‘including e.g. a subset of destinations or a receiver update number’ means that at least a reference to such destination of the subset of destinations or a reference to the receiver update number is included in the internet multicast packet at a predefined appropriate place.
Yet, a remark is that an ingress node is defined as being the first node, for distributing the multicast packets, of a domain of nodes. Such nodes might be routers or hosts whereby an ingress node can be a host or a router.
Furhtermore, it has to be remarked that according to step c) the multicast packet is forwarded towards the next hop. In fact, it is not the multicast packet but a replication i.e. a copy of the payload of the packet and a reconstruction of the header of the packet that is forwarded to the next hop. This is known according to the working of connectionless multicast system, but however, goes beyond the scope of the invention. The aim is that a replicate of the multicast packet is forwarded
Livens Wim
Ooms Dirk
Alcatel
Jones Prenell
Sughrue & Mion, PLLC
Vu Huy D.
LandOfFree
Method to forward a multicast packet, an ingress node and 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 Method to forward a multicast packet, an ingress node and a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method to forward a multicast packet, an ingress node and a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2968895