Routing support for point-to-multipoint connections

• US 6,529,498 B1
• Filed: 10/13/1998
• Issued: 03/04/2003
• Est. Priority Date: 04/28/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cheng, Dean
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US09/172,109
• Time in Patent Office: 1,603 Days
• Field of Search: 370/395, 370/230, 370/235, 370/237, 370/238, 370/248, 370/252, 370/256, 370/351, 370/384, 370/395.1, 370/395.2, 370/395.21, 370/395.3, 370/395.31, 370/395.32, 370/432
• US Class Current: 370/351
• 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/48 Routing tree calculation

Abstract

A distrubution tree for point-to-multipoint connections within a computer network may be dynamically created according to the number of connections shared by individual point-to-point connections which comprise the point-to-multipoint connection. Each distribution tree represents a collection of DTLs, overlapped from a root node of the tree to leaf nodes thereof. The distribution tree may be organized as a distribution table having two dimensions with row indices thereof comprising PNNI node indices of succeeding nodes along a connection DTL. Individual entries in a first column of the distribution table may indicate PNNI node indices of proceeding nodes along the connection DTL. Individual entries in a second column of the distribution table may indicate the number of point-to-point connections for the point-to-multipoint connection that use a link connecting a pair of proceeding and succeeding nodes. A path (or sub-path) may be selected from the distribution table in response to a request for a point-to-multipoint connection within the ATM network. Further, the distribution table may be updated in response to a call being added or dropped within the network.

Claims

1. A method comprising:

receiving information about routing selections; and

dynamically creating a distribution tree representing a point-to-multipoint connection within a computer network according to routing selections made for at least one point-to-point connection of the point-to-multipoint connection.

2. The method of claim 1 wherein the routing selections for the at least one point-to-point connection are made according to traffic metrics advertised for service classes within the network.

3. The method of claim 2 wherein the traffic metrics include administrative weight (AW), cell transfer delay (CTD) and cell delay variation (CDV).

4. The method of claim 3 wherein the service classes include constant bit rate (CBR), real-time variable bit rate (rtVBR), non-real-time variable bit rate (nrtVBR), available bit rate (ABR) and unspecified bit rate (UBR).

5. The method of claim 2 wherein the routing selections provide pre-computed routes within the computer network optimized to one of the traffic metrics.

6. The method of claim 5 wherein the distribution tree represents routes within the computer network optimized to share one or more of the routing selections of the at least one point-to-point connection.

7. The method of claim 1 wherein the distribution tree is represented as a multidimensional table stored in a computer-readable format.

8. A method comprising:

receiving information about a number of connections; and

dynamically generating a distribution table representing a point-to-multipoint connection supported by an ATM network according to the number of connections shared by individual point-to-point connections which comprise the point-to-multipoint connection.

9. The method of claim 8 wherein the distribution table is organized in a format having two dimensions with row indices thereof comprising PNNI node indices of succeeding nodes along a connection DTL.

10. The method of claim 9 wherein individual entries in a first column of the distribution table indicate PNNI node indices of proceeding nodes along the connection DTL.

11. The method of claim 10 wherein individual entries in a second column of the distribution table indicate the number of point-to-point connections for the point-to-multipoint connection that use a link connecting a pair of proceeding and succeeding nodes.

12. The method of claim 8 further comprising selecting a path from the distribution table in response to a request for a point-to-multipoint connection within the ATM network.

13. The method of claim 8 further comprising updating the distribution table in response to a call being added or dropped within the ATM network.

31. The apparatus of claim 8 further comprising means for updating the distribution table in response to a call being added or dropped within the ATM network.

14. A distribution table, comprising:

a first column including network indices of nodes along a connection path of one or more point-to-point connections of a point-to-multipoint connection within a network; and

a second column including values indicating the number of point-to-point connections for the point-to-multipoint connection that use a link connecting a pair of the nodes.

15. The distribution table of claim 14 wherein the network indices comprise PNNI node indices.

16. The distribution table of claim 15 wherein the network comprises an ATM network.

17. The distribution table of claim 14 wherein the first column is indexable using network indices of succeeding nodes along the connection path and for each index of one of the succeeding nodes, an entry in the first column indicates a proceeding node thereof.

18. The distribution table of claim 14 wherein the connection path comprises a path optimized according to the number of shared ones of the point-to-point connections of the point-to-multipoint connection.

19. An apparatus comprising:

means for receiving routing information about routing selections; and

means for dynamically creating a distribution tree representing a point-to-multipoint connection within a computer network according to routing selections made for at least one point-to-point connection of the point-to-multipoint connection.

20. The apparatus of claim 19 wherein the routing selections for the at least one point-to-point connection are made according to traffic metrics advertised for service classes within the network.

21. The apparatus of claim 20 wherein the traffic metrics include administrative weight (AW), cell transfer delay (CTD) and cell delay variation (CDV).

22. The apparatus of claim 21 wherein the service classes include constant bit rate (CBR), real-time variable bit rate (rtVBR), non-real-time variable bit rate (nrtVBR), available bit rate (ABR) and unspecified bit rate (UBR).

23. The apparatus of claim 20 wherein the routing selections provide pre-computed routes within the computer network optimized to one of the traffic metrics.

24. The apparatus of claim 23 wherein the distribution tree represents routes within the computer network optimized to share one or more of the routing selections of the at least one point-to-point connection.

25. The apparatus of claim 19 wherein the distribution tree is represented as a multidimensional table stored in a computer-readable format.

26. An apparatus comprising:

receiving information about a number of connections; and

means for dynamically generating a distribution table representing a point-to-multipoint connection supported by an ATM network according to the number of connections shared by individual point-to-point connections which comprise the point-to-multipoint connection.

27. The apparatus of claim 26 wherein the distribution table is organized in a format having two dimensions with row indices thereof comprising PNNI node indices of succeeding nodes along a connection DTL.

28. The apparatus of claim 27 wherein individual entries in a first column of the distribution table indicate PNNI node indices of proceeding nodes along the connection DTL.

29. The apparatus of claim 28 wherein individual entries in a second column of the distribution table indicate the number of point-to-point connections for the point-to-multipoint connection that use a link connecting a pair of proceeding and succeeding nodes.

30. The apparatus of claim 26 further comprising means for selecting a path from the distribution table in response to a request for a point-to-multipoint connection within the ATM network.