Method and apparatus for controlling fanout of a multicast tree

• US 6,785,245 B1
• Filed: 10/20/1999
• Issued: 08/31/2004
• Est. Priority Date: 10/20/1999
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Seddigh, Nabil, Lee, Cheng Y.
• Primary Examiner(s): LEE, CHI HO A
• Application Number:
  US09/422,106
• Time in Patent Office: 1,777 Days
• Field of Search: 370/254-256, 370/351, 370/400-401, 370/390, 370/392, 370/408, 709/225-226, 709/238
• US Class Current: 370/256
• CPC Class Codes: H04L 12/185 with management of multicast group membership

Abstract

A method as apparatus for controlling the number of egress points at an ingress node in a multicast tree in a differentiated services network is described. A resource management entity is provided in each edge node in the entity. The resource management entity in the ingress node stores data from a service level specification that specifies the bandwidth, type of service and a limit on the number of egress points that can be grafted to the ingress node. The grafting of egress points to the node is controlled by the limit. If a new egress point cannot be grafted to the ingress node, the downstream node requesting the graft is preferably provided with graft redirect options to permit the downstream node to graft to an existing branch of the multicast tree. The advantage is automated, dynamic control of the multicast tree so that service is delivered in accordance with a service level agreement that governs service delivery for the dynamic multicast tree.

Claims

1. A method of controlling fanout at an ingress node of a dynamic multicast tree for a multicast session in a differentiated services (DS) network, comprising the steps of:

a) receiving a graft request message from an egress node that has not been joined to the multicast tree;

b) determining whether a number of egress points specified by a service level specification (SLS) associated with the multicast session permits the egress node to be grafted;

c) if the graft is permitted, sending a graft permission response message to the egress node; and

if graft is not permitted a graft-redirect message is sent from the egress node to a downstream requesting node to permit the downstream requesting node to attempt to graft to an existing branch of the multicast tree.

2. A method as claimed in claim 1 wherein the graft-redirect message contains addresses of at least one grafted egress node that is already a part of the multicast tree, each grafted egress node providing an alternate site at which the downstream requesting node can attempt to graft to the multicast tree.

3. A method as claimed in claim 2 wherein the downstream requesting node forwards a graft request message to each of the at least one grafted egress nodes, in an order in which the addresses are presented in the graft-redirect message, and the downstream requesting node grafts to a first of the grafted egress node that accepts the graft.

4. A method as claimed in claim 3 wherein the downstream requesting node sends only one graft request message at a time and waits for a response from the grafted egress node to which the graft request message was sent before sending a next message.

5. A method as claimed in claim 4 wherein if each of the grafted egress nodes refuses to permit the downstream requesting node to graft, the graft attempt is aborted.

6. A method as claimed in claim 1 wherein in step (b) a graft permitted response message is sent from the ingress node if a number of egress points at the ingress is less than a maximum number permitted by the SLS.

7. A method as claimed in claim 1 wherein the SLS specifies a first service level when a number of grafted egress nodes is less than or equal to a first limit, and specifies a second service level if the number of grafted egress nodes is greater than the first limit.

8. A method as claimed in claim 7 wherein the ingress node marks packets associated with the multicast session with the first service level when the number of grafted egress nodes is less than or equal to the first limit.

9. A method as claimed in claim 8 wherein the ingress node marks packets associated with the multicast session with the second service level when the number of grafted egress nodes is greater than the first limit, thereby demoting the service level at the ingress node when the number of grafted egress nodes subtending the ingress node exceeds the first limit.

10. A method as claimed in claim 1 wherein the graft request message sent from the egress node is a router alert message.

11. A method as claimed in claim 1 wherein prior to sending the graft request message to the ingress node, the egress node receives a graft message from a downstream node wishing to graft to the multicast tree, and the graft message is diverted to a resource management entity resident in the egress node.

12. A method as claimed in claim 11 wherein the resource management entity sends a router alert towards the root of the multicast tree and this message is intercepted by an ingress node.

13. A methods as claimed in claim 12 wherein if the ingress node permits the graft, the resource management entity of the egress node provisions resources as a path for the multicast tree is set up to the ingress node.

14. A method as claimed in claim 1 wherein if a new egress node is added to the multicast tree, the new egress node requests a resource allocation along existing paths of the multicast tree;

in a hop-by-hop process.

15. An apparatus for controlling fanout at an ingress node of a dynamic multicast tree for a multicast session in a differentiated services network, comprising;

a resource management entity resident in an ingress node of the dynamic multicast tree, the resource management entity is programed to receive a service level specification (SLS) that specifies a level of service to be provided for the multicast session, and to store in a memory at least one variable defining a maximum number of egress points that may be grafted to the ingress node as specified by the SLS, and further adapted to accept graft request messages from egress nodes requesting to be grafted to the multicast tree, and to determine whether a graft requested in a graft request message is to be permitted given a value of the at least one variable and a number of pre-existing egress points at the ingress node, and the resource management entity in each egress node is further programmed to formulate a graft-redirect message that is sent to a downstream requesting node if the egress node cannot be grafted to the ingress node.

16. Apparatus as claimed in claim 15 wherein the redirect message formulated by the resource management entity of the egress node contains addresses of at least one grafted egress node that is already grafted to the multicast tree.

17. Apparatus as claimed in claim 16 wherein the at least one address is retrieved from a memory based on a relationship between the grafted egress node and the downstream node requesting to be grafted.

18. Apparatus as claimed in claim 17 wherein the relationship between the grafted egress nodes and the downstream node requesting to be grafted can be one of proximity, the at least one grafted egress node being a grafted egress node most proximate the downstream node requesting to be grafted.

19. Apparatus as claimed in claim 18 wherein the address of the at least one grafted egress node is stored in a memory.

20. Apparatus as claimed in claim 19 wherein the memory is a database resident on a server accessed by the resource management entity of the egress node.

21. Apparatus as claimed in claim 15 wherein the resource management entity is further programmed to store in the memory at least two variables defining at least first and second limits respecting a maximum number of egress points that may be grafted to the ingress node, and further adapted to store in the memory a service level associated with each of the at least first and second limits.

22. Apparatus as claimed in claim 21 wherein the ingress node is adapted to mark data packets associated with the multicast tree with a service level indicator that determines a quality of service for the data packets as they traverse the multicast tree.

23. Apparatus as claimed in claim 22 wherein the service level indicator with which the packets are marked is determined by the number of egress points from the ingress node, which is compared with each of the at least first and second limits to determine the service level indicator with which the data packets should be marked.

24. A system for controlling fanout at an ingress node of a dynamic multicast tree for a multicast session in a differentiated services network, comprising:

a plurality of edge nodes in the differentiated services network a selected one of the edge nodes being the ingress node, each of the edge nodes including a respective resource management entity programed to formulate, send and receive signaling messages related to the management of resources required for the multicast tree; and

the resource management entities of the edge nodes being further adapted to receive a service level specification (SLS) that specifies a level of service to be provided for the multicast session, and to store in a memory at least one variable respecting a maximum number of egress points that may be grafted to the ingress node for the multicast tree; and

if the ingress node cannot accept a graft request from another edge node in the differentiated services network, the resource management entity of the other edge node is programmed to send a graft-redirect message to a downstream requesting node to provide the downstream requesting node with an address of at least one egress node already grafted to the multicast tree.

25. The system as claimed in claim 24 wherein the ingress node is programed to receive a graft request message from another edge node in the differentiated services network requesting that the other edge node be permitted to graft to the ingress node of the multicast tree.

26. The system as claimed in claim 24 wherein the resource management entity of the ingress node is programed to determine, using the at least one variable respecting a maximum number of egress points, whether the other edge node can be grafted, and to respond to the other edge node with a response message to inform the other edge node whether it can be grafted to the ingress node.

27. The system as claimed in claim 26 wherein the resource management entity of the ingress node is programed to store at least two variables respecting the maximum number of egress points, the at least two variables providing at least first and second limits respecting the number of egress points that can be grafted to the edge node.

28. The system as claimed in claim 27 wherein the resource management entity of the ingress node is programmed to store in the memory at least two service level indicators respectively associated with each of the at least first and second limits, the service level indicators being used to mark data packets associated with the multicast session.

29. The system as claimed in claim 24 wherein the differentiated services network further includes a database that stores a map of the nodes in the network, the map providing an address of each node.

30. The system as claimed in claim 24 wherein the at least one address of the egress node already grafted to the multicast tree may be selected from the database on the basis of a proximity to the downstream requesting node to the edge node in the differentiated services network.

31. The system as claimed in claim 24 wherein when an edge node in the differentiated services network receives a permission to graft to the multicast tree, the resource management entity of the edge node provisions service resources as a path for the branch of the multicast tree.

32. A resource management entity for an edge node in a differentiated services network adapted to support dynamic multicast groups, comprising:

means for accepting a service level specification (SLS) that specifies a level of service for a multicast session and at least one variable for defining a maximum number of egress points that may be grafted to the edge router when the edge node serves as an ingress node of a multicast tree for a dynamic multicast session;

means for storing the at least one variable in a memory;

means for receiving a graft request message from another node in the differentiated services network, the graft request message requesting permission to graft as a new egress point to the ingress node;

means for determining whether the graft can be using the at least one variable for defining a maximum number of egress points;

means for informing the other node respecting whether the graft can be accepted; and

means for sending a graft-redirect message to a downstream requesting node when it is determined that the graft cannot be accepted, the graft-redirect message containing an address of at least one node already grafted to the multicast tree.

33. A resource management entity as claimed in claim 32 further including means for storing in the memory a service level indicator associated with each of the at least one variable, the service level indicator being used to mark data packets associated with the multicast session.

34. A resource management entity as claimed in claim 32 further including means for retrieving from a database the address of the at least one grafted node, the address being selected on a basis of proximity of the grafted node to the downstream requesting node.

35. A resource management entity as claimed in claim 32 further including means for dynamically provisioning resources as a path for branch of the multicast tree.