System, device, and method for reducing multicast forwarding states in a multicast communication system

• US 6,597,703 B1
• Filed: 11/29/1999
• Issued: 07/22/2003
• Est. Priority Date: 11/29/1999
• Status: Expired due to Term

• Current Assignee: Avaya Management L.P. (Avaya Incorporated)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Li, Yunzhou, Shieh, Shuching
• Primary Examiner(s): Yao, Kwang Bin
• Application Number:
  US09/450,100
• Time in Patent Office: 1,331 Days
• Field of Search: 370/254, 370/255, 370/389, 370/390, 370/392, 370/393, 370/395.3, 370/395.31, 370/428, 370/429, 370/432
• US Class Current: 370/428
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

A system, device, and method for reducing multicast forwarding states in a multicast communication system maintains forwarding states in such a way that the non-default forwarding states have non-overlapping source address ranges. Each forwarding state is associated with a source address range encompassing one or more source addresses. When a non-default forwarding state is installed, the source address range for the forwarding state is selected so that the source address range does not overlap with the source address ranges of any other non-default forwarding states. The source address range for a particular forwarding state may be adjusted as new routes are learned or existing routes are changed or aged.

Claims

1. In a multicast routing device having a multicast routing information base (MRIB) defining a number of enclosing ranges for multicast routes, each enclosing range characterized by a lower boundary and an upper boundary, a method for reducing the number of forwarding states maintained by the multicast routing device, each forwarding state including a source address (S), a group address (G), an inbound list identifying preferred and rejected inbound interfaces for the forwarding state, and an outbound list identifying outbound interfaces for the forwarding state, the method comprising:

associating with each forwarding state a source address range encompassing at least one source address, wherein a forwarding state having a source address range encompassing all possible source addresses is a default forwarding state, and a forwarding state having a source address range encompassing fewer than all possible source addresses is a non-default forwarding state; and

maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping.

2. The method of claim 1, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

detecting a multicast route change;

locating a forwarding state having a source address range that is contained in the changed multicast route;

searching in the MRIB to find an enclosing range for S, said enclosing range representing a matching range containing a number of more-specific enclosing ranges; and

updating the inbound and outbound interfaces for the forwarding state, if S is not contained in one of the number of more-specific enclosing ranges other than the changed multicast route and the changed multicast route causes the inbound interface for the forwarding state to change from an old inbound interface to a new inbound interface.

3. The method of claim 2, wherein updating the inbound and outbound interfaces for the forwarding state comprises:

changing the old inbound interface to be a rejected inbound interface for the forwarding state;

adding the new inbound interface to be a preferred inbound interface for the forwarding state;

determining whether the new inbound interface was an outbound interface for the forwarding state;

removing the new inbound interface from the forwarding state outbound list, if the new inbound interface was an outbound interface for the forwarding state;

determining whether the old inbound interface is an outbound interface for the forwarding state; and

adding the old inbound interface to the forwarding state outbound list, if the old inbound interface is determined to be an outbound interface for the forwarding state.

4. The method of claim 3, wherein determining whether the old inbound interface is an outbound interface for the forwarding state comprises consulting a multicast routing protocol.

5. The method of claim 2, wherein the changed multicast route is a new multicast route, and wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping further comprises:

finding a second forwarding state having a source address range that is less-specific than the new multicast route;

determining a new source address range for the second forwarding state; and

updating the second forwarding state to use the new source address range.

6. The method of claim 5, wherein determining the new source address range for the second forwarding state comprises:

determining that S is contained in the new multicast route;

setting the new source address range equal to a source address range associated with the multicast route.

7. The method of claim 5, wherein determining the new source address range for the second forwarding state comprises:

determining that S is not contained in the multicast route;

searching in the MRIB to find an enclosing range for S, said enclosing range representing a matching range containing a number of more-specific enclosing ranges;

determining that the matching range contains no more-specific enclosing ranges; and

setting the new source address range equal to a source address range associated with the multicast route.

8. The method of claim 5, wherein determining the new source address range for the second forwarding state comprises:

determining that S is not contained in the multicast route;

searching in the MRIB to find an enclosing range for S, said enclosing range representing a matching range containing a number of more-specific enclosing ranges;

determining that the matching range contains at least one more-specific enclosing range; and

determining the new source address range such that the new source address range does not overlap with any more-specific enclosing range within the matching range.

9. The method of claim 8, wherein determining the new source address range comprises:

determining a maximum upper boundary within the matching range that is less than or equal to S;

determining a minimum lower boundary within the matching range that is greater than or equal to S; and

determining the new source address range such that the lower boundary of the new source address range is greater than or equal to said maximum upper boundary and the upper boundary of the new source address range is less than or equal to said minimum lower boundary.

10. The method of claim 5, wherein updating the second forwarding state to use the new source address range comprises:

installing a new forwarding state having the new source address range;

copying the inbound list from the second forwarding state to the new forwarding state;

copying the outbound list from the second forwarding state to the new forwarding state; and

deleting the second forwarding state.

11. The method of claim 6, further comprising, after updating the second forwarding state to use the new source address range:

determining a next hop interface to the new multicast route;

changing the old inbound interface to be a rejected inbound interface for the updated forwarding state;

adding the new inbound interface to be a preferred inbound interface for the updated forwarding state;

determining whether the new inbound interface was an outbound interface for the second forwarding state;

removing the new inbound interface from the outbound list of the updated forwarding state, if the new inbound interface was an outbound interface for the second forwarding state;

determining whether the old inbound interface is an outbound interface for the updated forwarding state; and

adding the old inbound interface to the outbound list of the updated forwarding state, if the old inbound interface is determined to be an outbound interface for the updated forwarding state.

12. The method of claim 1, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

determining a multicast route to be aged;

searching in the MRIB to find a first enclosing range that contains the aged multicast route;

locating a forwarding state having a source address range that is contained in the aged multicast route;

searching in the MRIB to find a second enclosing range that contains S, said second enclosing range representing a matching range containing a number of more-specific enclosing ranges; and

updating the inbound and outbound interfaces for the forwarding state, if S is not contained in a more-specific enclosing range within the matching range other than the aged multicast route, the first enclosing range that contains the aged multicast route exists, and the aged multicast route causes the inbound interface of the forwarding state to change from an old inbound interface to a new inbound interface.

13. The method of claim 12, wherein updating the inbound and outbound interfaces for the forwarding state comprises:

changing the old inbound interface to be a rejected inbound interface for the forwarding state;

adding the new inbound interface to be a preferred inbound interface for the forwarding state;

determining whether the new inbound interface was an outbound interface for the forwarding state;

removing the new inbound interface from the outbound list of the forwarding state, if the new inbound interface was an outbound interface for the forwarding state;

determining whether the old inbound interface is an outbound interface for the forwarding state; and

adding the old inbound interface to the outbound list of the forwarding state, if the old inbound interface is determined to be an outbound interface for the forwarding state.

14. The method of claim 1, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a multicast packet for (S,G) from an interface;

installing a transitional most-specific forwarding state having a source address range encompassing only S;

determining all inbound and outbound interfaces for the transitional most-specific forwarding state; and

updating the transitional most-specific forwarding state to use a less-specific source address range, if all inbound and outbound interfaces agree to use the less-specific source address range.

15. The method of claim 1, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (*,G) request from an interface;

locating a default forwarding state associated with G; and

adding the interface to the outbound list of the default forwarding state.

16. The method of claim 1, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (*,G) request from an interface;

installing a default forwarding state associated with G;

determining a reverse path forwarding interface towards a rendezvous point device; and

adding the reverse path forwarding interface to the inbound list of the default forwarding state as a preferred inbound interface, if the reverse path forwarding interface is a sparse mode interface.

17. The method of claim 1, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (S,G) request from an interface;

locating a forwarding state having a source address range containing S; and

adding the interface to the outbound list of the forwarding state.

18. The method of claim 1, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (S,G) request from an interface;

determining a non-overlapping source address range for (S,G);

installing a forwarding state for (S,G) having said non-overlapping source address range;

copying the inbound list from a default forwarding state to the forwarding state for (S,G);

copying the outbound list from the default forwarding state to the forwarding state for (S,G); and

adding the interface to the outbound list of the forwarding state.

19. The method of claim 1, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a prune (*,G) request from an interface;

locating a default forwarding state associated with G;

removing the interface from the outbound list of the default forwarding state; and

deleting the default forwarding state, if the outbound list of the default forwarding state is empty.

20. The method of claim 1, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a prune (S,G) request from an interface;

locating a forwarding state having a source address range containing S, said forwarding state including a source list for each outbound interface in the outbound list;

deleting S from the source list associated with the interface;

removing the interface from the outbound list of the forwarding state, if the source list is empty; and

deleting the forwarding state, if the outbound list of the forwarding state is empty.

21. The method of claim 1, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a multicast packet for (S,G) from a sparse mode interface;

failing to locate a forwarding state having a source address range containing S; and

dropping the multicast packet without checking whether the sparse mode interface is an accepted inbound interface for (S,G).

22. The method of claim 21, further comprising:

installing a forwarding state for (S,G), the forwarding state including a “

drop”

indicator indicating that all multicast packets for (S,G) should be dropped.

23. The method of claim 1, wherein associating a source address range with a forwarding state comprises assigning a prefix to the forwarding state, the source address S and the prefix together defining the source address range for the forwarding state, such that a forwarding state having a prefix of zero (0) is a default forwarding state having a source address range encompassing all possible source addresses, and a forwarding state having a prefix greater than zero (0) is a non-default forwarding state having a source address range encompassing fewer than all possible source addresses.

24. The method of claim 23, wherein assigning a prefix to the forwarding state comprises:

searching the MRIB for a most-specific enclosing range that includes S, said most-specific enclosing range representing a matching range including a number of more-specific enclosing ranges; and

assigning the prefix to the forwarding state such that the source address range defined by the source address S and the prefix does not overlap with any of said more-specific enclosing ranges.

25. The method of claim 23, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

detecting a multicast route change;

locating a forwarding state (S/prefix,G) such that the source address range defined by S/prefix is contained in the changed multicast route;

searching in the MRIB to find an enclosing range for S, said enclosing range representing a matching range containing a number of more-specific enclosing ranges; and

updating the (S/prefix,G) inbound and outbound interfaces, if S is not contained in one of the number of more-specific enclosing ranges other than the changed multicast route and the changed multicast route causes the (S/prefix,G) inbound interface to change from an old inbound interface to a new inbound interface.

26. The method of claim 25, wherein updating the (S/prefix,G) inbound and outbound interfaces comprises:

changing the old inbound interface to be a rejected inbound interface for the (S/prefix,G) forwarding state;

adding the new inbound interface to be a preferred inbound interface for the (S/prefix,G) forwarding state;

determining whether the new inbound interface was an outbound interface for the (S/prefix,G) forwarding state;

removing the new inbound interface from the (S/prefix,G) outbound list, if the new inbound interface was an outbound interface for the (S/prefix,G) forwarding state;

determining whether the old inbound interface is an outbound interface for the (S/prefix,G) forwarding state; and

adding the old inbound interface to the (S/prefix,G) outbound list, if the old inbound interface is determined to be an outbound interface for the (S/prefix,G) forwarding state.

27. The method of claim 25, wherein the modified multicast route is a new multicast route, and wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping further comprises:

finding a second forwarding state having a source address range that is less-specific than the new multicast route;

determining a new prefix for the second forwarding state; and

re-prefixing the second forwarding state from an old prefix to the new prefix.

28. The method of claim 27, wherein determining the new prefix for the second forwarding state comprises:

determining that S is contained in the new multicast route;

setting the new prefix equal to a prefix associated with the new multicast route.

29. The method of claim 27, wherein determining the new prefix for the second forwarding state comprises:

determining that S is not contained in the new multicast route;

searching in the MRIB to find an enclosing range for S, said enclosing range representing a matching range containing a number of more-specific enclosing ranges;

determining that the matching range contains no more-specific enclosing ranges; and

setting the new prefix equal to a prefix associated with the matching range.

30. The method of claim 27, wherein determining the new prefix for the second forwarding state comprises:

determining that S is not contained in the new multicast route;

searching in the MRIB to find an enclosing range for S, said enclosing range representing a matching range containing a number of more-specific enclosing ranges;

determining that the matching range contains at least one more-specific enclosing range; and

determining the new prefix such that the source address range defined by S/prefix does not overlap with any more-specific enclosing range within the matching range.

31. The method of claim 30, wherein determining the new prefix comprises:

determining a maximum upper boundary within the matching range that is less than or equal to S;

determining a minimum lower boundary within the matching range that is greater than or equal to S; and

determining the new prefix such that the lower boundary of the source address range defined by S/prefix is greater than or equal to said maximum upper boundary and the upper boundary of the source address range defined by S/prefix is less than or equal to said minimum lower boundary.

32. The method of claim 31, wherein determining the new prefix such that the lower boundary of the source address range defined by S/prefix is greater than or equal to said maximum upper boundary and the upper boundary of the source address range defined by S/prefix is less than or equal to said minimum lower boundary comprises determining the minimum prefix such that the lower boundary of the source address range defined by S/prefix is greater than or equal to said maximum upper boundary and the upper boundary of the source address range defined by S/prefix is less than or equal to said minimum lower boundary.

33. The method of claim 27, wherein re-prefixing the second forwarding state from the old prefix to the new prefix comprises:

installing a new forwarding state (S/NewPrefix,G) for (S,G), where NewPrefix is the new prefix;

copying the inbound list from the second forwarding state to the (S/NewPrefix,G) inbound list;

copying the outbound list from the second forwarding state to the (S/NewPrefix,G) outbound list; and

deleting the second forwarding state.

34. The method of claim 28, further comprising, after re-prefixing the second forwarding state from an old prefix to the new prefix:

determining a next hop interface to the new multicast route;

changing the old inbound interface to be a rejected inbound interface for the re-prefixed forwarding state;

adding the new inbound interface to be a preferred inbound interface for the re-prefixed forwarding state;

determining whether the new inbound interface was an outbound interface for the second forwarding state;

removing the new inbound interface from the outbound list of the re-prefixed forwarding state, if the new inbound interface was an outbound interface for the second forwarding state;

determining whether the old inbound interface is an outbound interface for the re-prefixed forwarding state; and

adding the old inbound interface to the outbound list of the re-prefixed forwarding state, if the old inbound interface is determined to be an outbound interface for the re-prefixed forwarding state.

35. The method of claim 23, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

determining a multicast route to be aged;

searching in the MRIB to find a first enclosing range that contains the aged multicast route;

locating a forwarding state (S/prefix,G) such that the source address range defined by S/prefix is contained in the aged multicast route;

searching in the MRIB to find a second enclosing range that contains S, said second enclosing range representing a matching range containing a number of more-specific enclosing ranges; and

updating the (S/prefix,G) inbound and outbound interfaces, if S is not contained in a more-specific enclosing range within the matching range other than the aged multicast route, the first enclosing range that contains the aged multicast route exists, and the aged multicast route causes the (S/prefix,G) inbound interface to change from an old inbound interface to a new inbound interface.

36. The method of claim 35, wherein updating the (S/prefix,G) inbound and outbound interfaces comprises:

changing the old inbound interface to be a rejected inbound interface for the (S/prefix,G) forwarding state;

adding the new inbound interface to be a preferred inbound interface for the (S/prefix,G) forwarding state;

determining whether the new inbound interface was an outbound interface for the (S/prefix,G) forwarding state;

removing the new inbound interface from the (S/prefix,G) outbound list, if the new inbound interface was an outbound interface for the (S/prefix,G) forwarding state;

determining whether the old inbound interface is an outbound interface for the (S/prefix,G) forwarding state; and

adding the old inbound interface to the (S/prefix,G) outbound list, if the old inbound interface is determined to be an outbound interface for the (S/prefix,G) forwarding state.

37. The method of claim 23, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a multicast packet for (S,G) from an interface;

installing a transitional most-specific forwarding state having a source address range defined by S/prefix encompassing only S;

determining all inbound and outbound interfaces for the transitional most-specific forwarding state; and

re-prefixing the transitional most-specific forwarding state to use a less-specific prefix, if all inbound and outbound interfaces agree to use the less-specific prefix.

38. The method of claim 37, wherein the transitional most-specific forwarding state is assigned a prefix equal to thirty-two (32).

39. The method of claim 23, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (*,G) request from an interface;

locating a default forwarding state (0.0.0.0/0,G); and

adding the interface to the (0.0.0.0/0,G) outbound list.

40. The method of claim 23, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (*,G) request from an interface;

installing a default forwarding state (0.0.0.0/0,G);

determining a reverse path forwarding interface towards a rendezvous point device; and

adding the reverse path forwarding interface to the (0.0.0.0/0,G) inbound list as a referred inbound interface, if the reverse path forwarding interface is a sparse mode interface.

41. The method of claim 23, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (S,G) request from an interface;

locating a forwarding state having a source address range containing S; and

adding the interface to the outbound list of the forwarding state.

42. The method of claim 23, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (S,G) request from an interface;

computing a prefix for S;

installing a forwarding state for (S/prefix,G);

copying the inbound list from a default forwarding state (0.0.0.0/0,G) to the (S/prefix,G) inbound list;

copying the outbound list from a default forwarding state (0.0.0.0/0,G) to the (S/prefix,G) outbound list; and

adding the interface to the (S/prefix,G) outbound list.

43. The method of claim 23, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a prune (*,G) request from an interface;

locating a default forwarding state (0.0.0.0/0,G);

removing the interface from the (0.0.0.0/0,G) outbound list; and

deleting the default forwarding state (0.0.0.0/0,G), if the (0.0.0.0/0,G) outbound list is empty.

44. The method of claim 23, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a prune (S,G) request from an interface;

locating a forwarding state having a source address range containing S, said forwarding state including a source list for each outbound interface in the outbound list;

deleting S from the source list associated with the interface;

removing the interface from the outbound list of the forwarding state, if the source list is empty; and

deleting the forwarding state, if the outbound list of the forwarding state is empty.

45. The method of claim 23, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a multicast packet for (S,G) from a sparse mode interface;

failing to locate a forwarding state having a source address range containing S; and

dropping the multicast packet without checking whether the sparse mode interface is an accepted inbound interface for (S,G).

46. The method of claim 45, further comprising:

installing a forwarding state for (S,G), the forwarding state including a “

drop”

indicator indicating that all multicast packets for (S,G) should be dropped.

47. A device comprising:

a plurality of network interfaces;

a multicast routing information base (MRIB) for storing multicast routing information including a number of enclosing ranges for multicast routes, each enclosing range characterized by a lower boundary and an upper boundary;

a forwarding table for storing forwarding states, each forwarding state including a source address (S), a group address (G), an inbound list identifying preferred and rejected inbound interfaces for the forwarding state, and an outbound list identifying outbound interfaces for the forwarding state;

routing protocol logic operably coupled to determine multicast routes utilizing the plurality of network interfaces and store the multicast routes in the MRIB; and

table management logic responsive to multicast routing information obtained from the MRIB, the routing protocol logic, and the plurality of network interfaces, the table management logic operably coupled to associate with each forwarding state a source address range encompassing at least one source address, wherein a forwarding state having a source address range encompassing all possible source addresses is a default forwarding state and a forwarding state having a source address range encompassing fewer than all possible source addresses is a non-default forwarding state, and to maintain the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping.

48. The device of claim 47, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

detecting a multicast route change;

locating in the forwarding table a forwarding state having a source address range that is contained in the changed multicast route;

searching in the MRIB to find an enclosing range for S, said enclosing range representing a matching range containing a number of more-specific enclosing ranges; and

updating the inbound and outbound interfaces for the forwarding state, if S is not contained in one of the number of more-specific enclosing ranges other than the changed multicast route and the changed multicast route causes the inbound interface for the forwarding state to change from an old inbound interface to a new inbound interface.

49. The device of claim 48, wherein updating the inbound and outbound interfaces for the forwarding state comprises:

changing the old inbound interface to be a rejected inbound interface for the forwarding state;

adding the new inbound interface to be a preferred inbound interface for the forwarding state;

determining whether the new inbound interface was an outbound interface for the forwarding state;

removing the new inbound interface from the forwarding state outbound list, if the new inbound interface was an outbound interface for the forwarding state;

determining whether the old inbound interface is an outbound interface for the forwarding state; and

adding the old inbound interface to the forwarding state outbound list, if the old inbound interface is determined to be an outbound interface for the forwarding state.

50. The device of claim 49, wherein determining whether the old inbound interface is an outbound interface for the forwarding state comprises consulting the routing protocol logic.

51. The device of claim 48, wherein the changed multicast route is a new multicast route, and wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping further comprises:

finding in the forwarding table a second forwarding state having a source address range that is less-specific than the new multicast route;

determining a new source address range for the second forwarding state; and

updating the second forwarding state to use the new source address range.

52. The device of claim 50, wherein determining the new source address range for the second forwarding state comprises:

determining that S is contained in the new multicast route;

setting the new source address range equal to a source address range associated with the multicast route.

53. The device of claim 50, wherein determining the new source address range for the second forwarding state comprises:

determining that S is not contained in the multicast route;

searching in the MRIB to find an enclosing range for S, said enclosing range representing a matching range containing a number of more-specific enclosing ranges;

determining that the matching range contains no more-specific enclosing ranges; and

setting the new source address range equal to a source address range associated with the multicast route.

54. The device of claim 50, wherein determining the new source address range for the second forwarding state comprises:

determining that S is not contained in the multicast route;

searching in the MRIB to find an enclosing range for S, said enclosing range representing a matching range containing a number of more-specific enclosing ranges;

determining that the matching range contains at least one more-specific enclosing range; and

determining the new source address range such that the new source address range does not overlap with any more-specific enclosing range within the matching range.

55. The device of claim 54, wherein determining the new source address range comprises:

determining a maximum upper boundary within the matching range that is less than or equal to S;

determining a minimum lower boundary within the matching range that is greater than or equal to S; and

determining the new source address range such that the lower boundary of the new source address range is greater than or equal to said maximum upper boundary and the upper boundary of the new source address range is less than or equal to said minimum lower boundary.

56. The device of claim 50, wherein updating the second forwarding state to use the new source address range comprises:

installing in the forwarding table a new forwarding state having the new source address range;

copying the inbound list from the second forwarding state to the new forwarding state;

copying the outbound list from the second forwarding state to the new forwarding state; and

deleting the second forwarding state from the forwarding table.

57. The device of claim 51, further comprising, after updating the second forwarding state to use the new source address range:

consulting the routing protocol logic to determine a next hop interface to the new multicast route;

changing the old inbound interface to be a rejected inbound interface for the updated forwarding state;

adding the new inbound interface to be a preferred inbound interface for the updated forwarding state;

determining whether the new inbound interface was an outbound interface for the second forwarding state;

removing the new inbound interface from the outbound list of the updated forwarding state, if the new inbound interface was an outbound interface for the second forwarding state;

determining whether the old inbound interface is an outbound interface for the updated forwarding state; and

adding the old inbound interface to the outbound list of the updated forwarding state, if the old inbound interface is determined to be an outbound interface for the updated forwarding state.

58. The device of claim 47, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

determining a multicast route to be aged;

searching in the MRIB to find a first enclosing range that contains the aged multicast route;

locating in the forwarding table a forwarding state having a source address range that is contained in the aged multicast route;

searching in the MRIB to find a second enclosing range that contains S, said second enclosing range representing a matching range containing a number of more-specific enclosing ranges; and

updating the inbound and outbound interfaces for the forwarding state, if S is not contained in a more-specific enclosing range within the matching range other than the aged multicast route, the first enclosing range that contains the aged multicast route exists, and the aged multicast route causes the inbound interface of the forwarding state to change from an old inbound interface to a new inbound interface.

59. The device of claim 58, wherein updating the inbound and outbound interfaces for the forwarding state comprises:

changing the old inbound interface to be a rejected inbound interface for the forwarding state;

adding the new inbound interface to be a preferred inbound interface for the forwarding state;

determining whether the new inbound interface was an outbound interface for the forwarding state;

removing the new inbound interface from the outbound list of the forwarding state, if the new inbound interface was an outbound interface for the forwarding state;

determining whether the old inbound interface is an outbound interface for the forwarding state; and

adding the old inbound interface to the outbound list of the forwarding state, if the old inbound interface is determined to be an outbound interface for the forwarding state.

60. The device of claim 47, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a multicast packet for (S,G) from one of the plurality of network interfaces;

installing in the forwarding table a transitional most-specific forwarding state having a source address range encompassing only S;

determining all inbound and outbound interfaces for the transitional most-specific forwarding state; and

updating the transitional most-specific forwarding state to use a less-specific source address range, if all inbound and outbound interfaces agree to use the less-specific source address range.

61. The device of claim 47, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (*,G) request from one of the plurality of network interfaces;

locating in the forwarding table a default forwarding state associated with G; and

adding the network interface to the outbound list of the default forwarding state.

62. The device of claim 47, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (*,G) request from one of the plurality of network interfaces;

installing in the forwarding table a default forwarding state associated with G;

consulting the routing protocol logic to determine a reverse path forwarding interface towards a rendezvous point device; and

adding the reverse path forwarding interface to the inbound list of the default forwarding state as a preferred inbound interface, if the reverse path forwarding interface is a sparse mode interface.

63. The device of claim 47, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (S,G) request from one of the plurality of network interfaces;

locating in the forwarding table a forwarding state having a source address range containing S; and

adding the network interface to the outbound list of the forwarding state.

64. The device of claim 47, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (S,G) request from one of the plurality of network interfaces;

determining a non-overlapping source address range for (S,G);

installing in the forwarding table a forwarding state for (S,G) having said non-overlapping source address range;

copying the inbound list from a default forwarding state to the forwarding state for (S,G);

copying the outbound list from the default forwarding state to the forwarding state for (S,G); and

adding the interface to the outbound list of the forwarding state.

65. The device of claim 47, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a prune (*,G) request from one of the plurality of network interfaces;

locating in the forwarding table a default forwarding state associated with G;

removing the interface from the outbound list of the default forwarding state; and

deleting the default forwarding state from the forwarding table, if the outbound list of the default forwarding state is empty.

66. The device of claim 47, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a prune (S,G) request from one of the plurality of network interfaces;

locating in the forwarding table a forwarding state having a source address range containing S, said forwarding state including a source list for each outbound interface in the outbound list;

deleting S from the source list associated with the interface;

removing the interface from the outbound list of the forwarding state, if the source list is empty; and

deleting the forwarding state from the forwarding table, if the outbound list of the forwarding state is empty.

67. The device of claim 47, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a multicast packet for (S,G) from a sparse mode interface;

failing to locate a forwarding state in the forwarding table having a source address range containing S; and

dropping the multicast packet without consulting the routing protocol logic to determine whether the sparse mode interface is an accepted inbound interface for (S,G).

68. The device of claim 67, further comprising:

installing in the forwarding table a forwarding state for (S,G), the forwarding state including a “

drop”

indicator indicating that all multicast packets for (S,G) should be dropped.

69. The device of claim 47, wherein associating a source address range with a forwarding state comprises assigning a prefix to the forwarding state, the source address S and the prefix together defining the source address range for the forwarding state, such that a forwarding state having a prefix of zero (0) is a default forwarding state having a source address range encompassing all possible source addresses, and a forwarding state having a prefix greater than zero (0) is a non-default forwarding state having a source address range encompassing fewer than all possible source addresses.

70. The device of claim 69, wherein assigning a prefix to the forwarding state comprises:

searching the MRIB for a most-specific enclosing range that includes S, said most-specific enclosing range representing a matching range including a number of more-specific enclosing ranges; and

assigning the prefix to the forwarding state such that the source address range defined by the source address S and the prefix does not overlap with any of said more-specific enclosing ranges.

71. The device of claim 69, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

detecting a multicast route change;

locating in the forwarding table a forwarding state (S/prefix,G) such that the source address range defined by S/prefix is contained in the changed multicast route;

searching in the MRIB to find an enclosing range for S, said enclosing range representing a matching range containing a number of more-specific enclosing ranges; and

updating the (S/prefix,G) inbound and outbound interfaces, if S is not contained in one of the number of more-specific enclosing ranges other than the changed multicast route and the changed multicast route causes the (S/prefix,G) inbound interface to change from an old inbound interface to a new inbound interface.

72. The device of claim 71, wherein updating the (S/prefix,G) inbound and outbound interfaces comprises:

changing the old inbound interface to be a rejected inbound interface for the (S/prefix,G) forwarding state;

adding the new inbound interface to be a preferred inbound interface for the (S/prefix,G) forwarding state;

determining whether the new inbound interface was an outbound interface for the (S/prefix,G) forwarding state;

removing the new inbound interface from the (S/prefix,G) outbound list, if the new inbound interface was an outbound interface for the (S/prefix,G) forwarding state;

determining whether the old inbound interface is an outbound interface for the (S/prefix,G) forwarding state; and

adding the old inbound interface to the (S/prefix,G) outbound list, if the old inbound interface is determined to be an outbound interface for the (S/prefix,G) forwarding state.

73. The device of claim 71, wherein the modified multicast route is a new multicast route, and wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping further comprises:

finding in the forwarding table a second forwarding state having a source address range that is less-specific than the new multicast route;

determining a new prefix for the second forwarding state; and

re-prefixing the second forwarding state from an old prefix to the new prefix.

74. The device of claim 73, wherein determining the new prefix for the second forwarding state comprises:

determining that S is contained in the new multicast route;

setting the new prefix equal to a prefix associated with the new multicast route.

75. The device of claim 73, wherein determining the new prefix for the second forwarding state comprises:

determining that S is not contained in the new multicast route;

searching in the MRIB to find an enclosing range for S, said enclosing range representing a matching range containing a number of more-specific enclosing ranges;

determining that the matching range contains no more-specific enclosing ranges; and

setting the new prefix equal to a prefix associated with the matching range.

76. The device of claim 73, wherein determining the new prefix for the second forwarding state comprises:

determining that S is not contained in the new multicast route;

searching in the MRIB to find an enclosing range for S, said enclosing range representing a matching range containing a number of more-specific enclosing ranges;

determining that the matching range contains at least one more-specific enclosing range; and

determining the new prefix such that the source address range defined by S/prefix does not overlap with any more-specific enclosing range within the matching range.

77. The device of claim 76, wherein determining the new prefix comprises:

determining a maximum upper boundary within the matching range that is less than or equal to S;

determining a minimum lower boundary within the matching range that is greater than or equal to S; and

determining the new prefix such that the lower boundary of the source address range defined by S/prefix is greater than or equal to said maximum upper boundary and the upper boundary of the source address range defined by S/prefix is less than or equal to said minimum lower boundary.

78. The device of claim 77, wherein determining the new prefix such that the lower boundary of the source address range defined by S/prefix is greater than or equal to said maximum upper boundary and the upper boundary of the source address range defined by S/prefix is less than or equal to said minimum lower boundary comprises determining the minimum prefix such that the lower boundary of the source address range defined by S/prefix is greater than or equal to said maximum upper boundary and the upper boundary of the source address range defined by S/prefix is less than or equal to said minimum lower boundary.

79. The device of claim 73, wherein re-prefixing the second forwarding state from the old prefix to the new prefix comprises:

installing in the forwarding table a new forwarding state (S/NewPrefix,G) for (S,G), where NewPrefix is the new prefix;

copying the inbound list from the second forwarding state to the (S/NewPrefix,G) inbound list;

copying the outbound list from the second forwarding state to the (S/NewPrefix,G) outbound list; and

deleting the second forwarding state from the forwarding table.

80. The device of claim 74, further comprising, after re-prefixing the second forwarding state from an old prefix to the new prefix:

consulting the routing protocol logic to determine a next hop interface to the new multicast route;

changing the old inbound interface to be a rejected inbound interface for the re-prefixed forwarding state;

adding the new inbound interface to be a preferred inbound interface for the re-prefixed forwarding state;

determining whether the new inbound interface was an outbound interface for the second forwarding state;

removing the new inbound interface from the outbound list of the re-prefixed forwarding state, if the new inbound interface was an outbound interface for the second forwarding state;

determining whether the old inbound interface is an outbound interface for the re-prefixed forwarding state; and

adding the old inbound interface to the outbound list of the re-prefixed forwarding state, if the old inbound interface is determined to be an outbound interface for the re-prefixed forwarding state.

81. The device of claim 69, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

determining a multicast route to be aged;

searching in the MRIB to find a first enclosing range that contains the aged multicast route;

locating in the forwarding table a forwarding state (S/prefix,G) such that the source address range defined by S/prefix is contained in the aged multicast route;

searching in the MRIB to find a second enclosing range that contains S, said second enclosing range representing a matching range containing a number of more-specific enclosing ranges; and

updating the (S/prefix,G) inbound and outbound interfaces, if S is not contained in a more-specific enclosing range within the matching range other than the aged multicast route, the first enclosing range that contains the aged multicast route exists, and the aged multicast route causes the (S/prefix,G) inbound interface to change from an old inbound interface to a new inbound interface.

82. The device of claim 81, wherein updating the (S/prefix,G) inbound and outbound interfaces comprises:

changing the old inbound interface to be a rejected inbound interface for the (S/prefix,G) forwarding state;

adding the new inbound interface to be a preferred inbound interface for the (S/prefix,G) forwarding state;

determining whether the new inbound interface was an outbound interface for the (S/prefix,G) forwarding state;

removing the new inbound interface from the (S/prefix,G) outbound list, if the new inbound interface was an outbound interface for the (S/prefix,G) forwarding state;

determining whether the old inbound interface is an outbound interface for the (S/prefix,G) forwarding state; and

adding the old inbound interface to the (S/prefix,G) outbound list, if the old inbound interface is determined to be an outbound interface for the (S/prefix,G) forwarding state.

83. The device of claim 69, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a multicast packet for (S,G) from one of the plurality of network interfaces;

installing in the forwarding table a transitional most-specific forwarding state having a source address range defined by S/prefix encompassing only S;

determining all inbound and outbound interfaces for the transitional most-specific forwarding state; and

re-prefixing the transitional most-specific forwarding state to use a less-specific prefix, if all inbound and outbound interfaces agree to use the less-specific prefix.

84. The device of claim 83, wherein the transitional most-specific forwarding state is assigned a prefix equal to thirty-two (32).

85. The device of claim 69, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (*,G) request from one of the plurality of network interfaces;

locating in the forwarding table a default forwarding state (0.0.0.0/0,G); and

adding the interface to the (0.0.0.0/0,G) outbound list.

86. The device of claim 69, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (*,G) request from one of the plurality of network interfaces;

installing in the forwarding table a default forwarding state (0.0.0.0/0,G);

consulting the routing protocol logic to determine a reverse path forwarding interface towards a rendezvous point device; and

adding the reverse path forwarding interface to the (0.0.0.0/0,G) inbound list as a preferred inbound interface, if the reverse path forwarding interface is a sparse mode interface.

87. The device of claim 69, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (S,G) request from one of the plurality of network interfaces;

locating in the forwarding table a forwarding state having a source address range containing S; and

adding the interface to the outbound list of the forwarding state.

88. The device of claim 69, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a join (S,G) request from one of the plurality of network interfaces;

computing a prefix for S;

installing in the forwarding table a forwarding state for (S/prefix,G);

copying the inbound list from a default forwarding state (0.0.0.0/0,G) to the (S/prefix,G) inbound list;

copying the outbound list from a default forwarding state (0.0.0.0/0,G) to the (S/prefix,G) outbound list; and

adding the interface to the (S/prefix,G) outbound list.

89. The device of claim 69, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a prune (*,G) request from one of the plurality of network interfaces;

locating in the forwarding table a default forwarding state (0.0.0.0/0,G);

removing the interface from the (0.0.0.0/0,G) outbound list; and

deleting the default forwarding state (0.0.0.0/0,G) from the forwarding table, if the (0.0.0.0/0,G) outbound list is empty.

90. The device of claim 69, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a prune (S,G) request from one of the plurality of network interfaces;

locating in the forwarding table a forwarding state having a source address range containing S, said forwarding state including a source list for each outbound interface in the outbound list;

deleting S from the source list associated with the interface;

removing the interface from the outbound list of the forwarding state, if the source list is empty; and

deleting the forwarding state from the forwarding table, if the outbound list of the forwarding state is empty.

91. The device of claim 69, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a multicast packet for (S,G) from a sparse mode interface;

failing to locate a forwarding state in the forwarding table having a source address range containing S; and

dropping the multicast packet without consulting with the routing protocol logic to determine whether the sparse mode interface is an accepted inbound interface for (S,G).

92. The device of claim 91, further comprising:

installing in the forwarding table a forwarding state for (S,G), the forwarding state including a “

drop”

indicator indicating that all multicast packets for (S,G) should be dropped.

93. A program product comprising a computer readable medium having embodied therein a computer program for reducing the number of forwarding states in a multicast routing device, the multicast routing device having a forwarding table for storing forwarding states, each forwarding state including a source address (S), a group address (G), an inbound list identifying preferred and rejected inbound interfaces for the forwarding state, and an outbound list identifying outbound interfaces for the forwarding state, and a multicast routing information base (MRIB) for storing multicast routing information including a number of enclosing ranges for multicast routes, each enclosing range characterized by a lower boundary and an upper boundary, the computer program comprising:

routing protocol logic operably coupled to determine multicast routes utilizing a plurality of network interfaces and store the multicast routes in the MRIB; and

table management logic responsive to multicast routing information obtained from the MRIB, the routing protocol logic, and the plurality of network interfaces, the table management logic programmed to associate with each forwarding state a source address range encompassing at least one source address, wherein a forwarding state having a source address range encompassing all possible source addresses is a default forwarding state and a forwarding state having a source address range encompassing fewer than all possible source addresses is a non-default forwarding state, and to maintain the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping.

94. The program product of claim 93, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

detecting a multicast route change;

locating in the forwarding table a forwarding state having a source address range that is contained in the changed multicast route;

searching in the MRIB to find an enclosing range for S, said enclosing range representing a matching range containing a number of more-specific enclosing ranges; and

updating the inbound and outbound interfaces for the forwarding state, if S is not contained in one of the number of more-specific enclosing ranges other than the changed multicast route and the changed multicast route causes the inbound interface for the forwarding state to change from an old inbound interface to a new inbound interface.

95. The program product of claim 93, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

determining a multicast route to be aged;

searching in the MRIB to find a first enclosing range that contains the aged multicast route;

locating in the forwarding table a forwarding state having a source address range that is contained in the aged multicast route;

searching in the MRIB to find a second enclosing range that contains S, said second enclosing range representing a matching range containing a number of more-specific enclosing ranges; and

updating the inbound and outbound interfaces for the forwarding state, if S is not contained in a more-specific enclosing range within the matching range other than the aged multicast route, the first enclosing range that contains the aged multicast route exists, and the aged multicast route causes the inbound interface of the forwarding state to change from an old inbound interface to a new inbound interface.

96. The program product of claim 93, wherein maintaining the forwarding states such that the source address ranges for all non-default forwarding states are non-overlapping comprises:

receiving a multicast packet for (S,G) from one of the plurality of network interfaces;

installing in the forwarding table a transitional most-specific forwarding state having a source address range encompassing only S;

determining all inbound and outbound interfaces for the transitional most-specific forwarding state; and

updating the transitional most-specific forwarding state to use a less-specific source address range, if all inbound and outbound interfaces agree to use the less-specific source address range.

97. The program product of claim 93, wherein associating a source address range with a forwarding state comprises assigning a prefix to the forwarding state, the source address S and the prefix together defining the source address range for the forwarding state, such that a forwarding state having a prefix of zero (0) is a default forwarding state having a source address range encompassing all possible source addresses, and a forwarding state having a prefix greater than zero (0) is a non-default forwarding state having a source address range encompassing fewer than all possible source addresses.