Multicast routing with nearest queue first allocation and dynamic and static vector quantization

• US 6,760,331 B1
• Filed: 03/31/1999
• Issued: 07/06/2004
• Est. Priority Date: 03/31/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Moussavi, Farshid, Shah, Dhaval N.
• Primary Examiner(s): Duong, Frank
• Assistant Examiner(s): Harper, Kevin C.
• Application Number:
  US09/283,109
• Time in Patent Office: 1,924 Days
• Field of Search: 370/389, 370/390, 370/412-418, 370/428, 370/429
• US Class Current: 370/390
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/3045 Virtual queuing

Abstract

The invention includes a way to route multicast traffic through a switch or other device that uses input queuing. Basis vectors are associated with each virtual queue, which in a preferred embodiment are multicast virtual output queues (MVOQs). Each incoming flow is allocated to the MVOQ whose basis vector is closest to the destination vector of the incoming flow, creating queues whose contents are distinct from each other in terms of destination addresses of the flows in the respective queue. To optimize for traffic encountered basis vectors can be chosen using vector quantization methods. Basis vectors can be set statically or can be selected and updated dynamically, responsive to the traffic encountered or as set by an operator. The invention can reduce the number of virtual queues required for a given incremental improvement in performance or can improve performance for a given number of virtual queues.

Claims

1. A method for handling multicast flows in a switching device comprising:

receiving a multicast message at an input interface, where said multicast message has an associated destination vector;

associating a basis vector with each multicast virtual output queue of a set of multicast virtual output queues, said set of multicast virtual output queues having more than one and less than 2^N individual multicast virtual output queues for said input interface, where N equals the number of individual output interfaces to which the said multicast message could be directed;

selecting a basis vector, as a selected basis vector, by comparing said destination vector of said multicast message with each said basis vector; and

assigning said multicast message to a multicast virtual output queue associated with said selected basis vector.

2. A method as in claim 1 wherein said comparing involves determining a distance measure between said destination vector and each said basis vector.

3. A method as in claim 2 wherein said distance measure is a square of a Euclidean distance.

4. A method as in claim 2 further comprising:

calculating said distance measure using a content addressable memory.

5. A method as in claim 2 further comprising:

calculating said distance measure for destination vector {right arrow over (D)} and basis vector {right arrow over (B)} where both are of N dimensions, as $\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(d_i-b_i\right)}^2.$

6. A method as in claim 1 further comprising:

computing an updated basis vector in response to said destination vector of said multicast message.

7. A method as in claim 6 further comprising:

saving updated basis vectors in memory; and

substituting said updated basis vectors for use as basis vectors in said associating step in response to expiration of a window count.

8. A method as in claim 6 further comprising:

computing said updated basis vector by the expression $\stackrel{\to <br><br>}{\mathrm{UB}}=\frac{\left[\stackrel{\to <br><br>}{\mathrm{SB}}+\left(\stackrel{\to <br><br>}{D}*\mathrm{CW}\right)\right]}{\left(1+\mathrm{CW}\right)}$

where {right arrow over (UB)} is said updated basis vector, {right arrow over (SB)} is said selected basis vector, {right arrow over (D)} is said destination vector, and CW is a centroid weight.

9. A method as in claim 8 where CW=0.1.

10. A method as in claim 8 where CW equals the centroid of said selected basis vector and said destination vector.

11. A method as in claim 1 further comprising:

sending a head element of a multicast virtual output queue of said set of multicast virtual output queues to output interfaces.

39. A computer readable media comprising:

said computer readable media containing executable program instruction for the practice of the method of claim 1 or claim 12 or claim 20 or claim 30.

40. Electromagnetic signals propagating on a computer network, comprising:

said electromagnetic signals carrying instruction for the practice of the method of claim 1 or claim 12 or claim 20 or claim 30.

12. A method of routing a packet having an associated destination vector, said packet arriving at an input interface of a switching device, including steps for:

establishing a set of multicast virtual output queues for said input interface;

determining whether said packet is part of an existing flow;

if said packet is part of an existing flow, assigning said packet to one of said set of multicast virtual output queues associated with said existing flow;

if said packet is not part of an existing flow, assigning said packet to one of said set of multicast virtual output queues responsive to said destination vector; and

queuing said packet in said one multicast virtual output queue.

13. A method as in claim 12 wherein said step of assigning includes steps of:

if said packet is part of an existing flow, updating a flow table entry associated with said destination vector;

if said packet is not part of an existing flow, creating a flow table entry associated with said destination vector and said one multicast virtual output queues.

14. A method as in claim 13 including further steps of:

adjusting a copy of said basis vector associated with said one multicast virtual output queues;

incrementing a counter of a number of packets processed; and

updating each said basis vector associated with each of said set of multicast virtual output queues in response to a comparison between said counter and said selected window length.

15. A method as in claim 12, including steps of:

updating said basis vector associated with said one multicast virtual output queueS.

16. A method as in claim 15 wherein said step of updating includes steps of:

replacing said basis vector with the centroid of said basis vector and said destination vector.

17. A method as in claim 15 wherein said step of updating includes steps of:

adjusting said basis vector by an amount calculated using a fixed centroid weight and said destination vector.

18. A method as in claim 17 wherein said basis vector includes elements and said destination vector includes elements, and wherein said step of adjusting includes steps for:

adding to each element of said basis vector the product of the respective each element of said destination vector and said fixed centroid weight;

dividing each element of said basis vector by the sum of unity and said fixed centroid weight.

19. A method as in claim 18 wherein said packet includes a single cell.

20. A method for routing a packet arriving at a multicast input interface of a switching device, said packet having an associated destination vector, including steps for:

associating a basis vector with each multicast virtual output queue of a set of multicast virtual output queues to create a set of basis vectors;

selecting a multicast virtual output queue responsive to a comparison of said destination vector with said set of basis vectors; and

queuing said packet in said multicast virtual output queue.

21. A method as in claim 20 further comprising:

computing an updated basis vector in response to said destination vector of said multicast message.

22. A method as in claim 21 further comprising:

computing said updated basis vector by the expression $\stackrel{\to <br><br>}{\mathrm{UB}}=\frac{\left[\stackrel{\to <br><br>}{\mathrm{SB}}+\left(\stackrel{\to <br><br>}{D}*\mathrm{CW}\right)\right]}{\left(1+\mathrm{CW}\right)}$

where {right arrow over (UB)} is said updated basis vector, {right arrow over (S)} B is said selected basis vector, {right arrow over (D)} is said destination vector, and CW is a centroid weight.

23. A method as in claim 22 further comprising:

setting CW=0.1.

24. A method as in claim 22 further comprising:

setting CW equal the centroid of said selected basis vector and said destination vector.

25. A method as in claim 21 further comprising:

saving updated basis vectors in memory; and

substituting said updated basis vectors for use as basis vectors in response to expiration of a window count.

26. A method as in claim 20 further comprising:

determining a distance measure between said destination vector and each said basis vector in said comparing said destination vector with each said basis vector.

28. A method as in claim 26 further comprising:

calculating said distance measure for destination vector {right arrow over (D)} and basis vector {right arrow over (B)} where both are of N dimensions, as $\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(d_i-b_i\right)}^2.$

29. A method as in claim 26 further comprising:

calculating said distance measure using a content addressable memory.

83. A method as in claim 20 further comprising:

sending a head element of a multicast virtual output queue of said set of multicast virtual output queues to output interfaces.

30. A method for operating a switching device, said switching device having an input interface, said input interface having multicast capability, comprising:

establishing a set of multicast virtual output queues for said input interface;

choosing a set of basis vectors for said set of multicast virtual output queues;

associating each basis vector of said set of basis vectors with a multicast virtual out-put queue of said set of multicast virtual output queues;

receiving a message having an associated direction vector at said input interface;

queuing said message in a multicast virtual output queue in response to a comparison between said direction vector and said set of basis vectors.

27. A method as in claim 36 further comprising:

computing distance measure as a square of a Euclidean distance.

31. A method as in claim 30 wherein said set of basis vectors are in a continuous bitmap subspace.

32. A method as in claim 30 wherein said set of basis vectors are in a discrete bitmap subspace.

33. A method as in claim 30 wherein said set of basis vectors are substantially orthogonal.

34. A method as in claim 30 wherein the sum of a distance measure between said set of basis vectors and a set of destination vectors is minimized.

35. A method as in claim 30 wherein at least one of said basis vectors includes a broadcast vector.

36. A method as in claim 30 wherein said step of choosing includes using vector quantization methods.

37. A method as in claim 30 wherein said step of choosing includes using a modified Lloyd Max quantizer.

38. A method as in claim 30 wherein said step of choosing includes setting at least one of said basis vectors to be a predetermined vector.

41. An apparatus having at least one processor and at least one memory coupled to said at least one processor, said apparatus comprising:

a reception module configured to receive a multicast message at an input interface, where said multicast message has an associated destination vector;

an association module configured to associate a basis vector with each multicast virtual output queue of a selected set of multicast virtual output queues, said set of multicast virtual output queues having more than one and less than 2^N individual multicast virtual out-put queues for said input interface, where N equals the number of individual output interfaces to which the said multicast message could be directed;

a selection module configured to select a basis vector, as a selected basis vector, by comparing said destination vector of said multicast message with each said basis vector; and

an assignment module to assign said multicast message to a multicast virtual output queue associated with said selected basis vector.

42. The apparatus of claim 41 wherein said comparing involves determining a distance measure between said destination vector and each said basis vector.

43. The apparatus of claim 42 wherein said distance measure is a square of a Euclidean distance.

44. An apparatus of claim 41 further comprising:

a send module configured to send a head element of a multicast virtual output queue of said set of multicast virtual output queues to output interfaces.

45. An apparatus for routing a packet having an associated destination vector arriving at an input interface of a switching device, said input interface having at least one processor and at least one memory coupled to said at least one processor, said apparatus including:

a set of multicast virtual output queues for said input interface;

a determination module configured to determine whether said packet is part of an existing flow;

a first assignment module configured to assign said packet to one of said set of multicast virtual output queues associated with said existing flow responsive to a positive determination by said determination module;

a second assignment module configured to assign said packet to one of said set of multicast virtual output queues responsive to said destination vector responsive to a negative determination by said determination module; and

a queuing module configured to queue said packet in said one multicast virtual output queue.

46. The apparatus of claim 45 wherein said first assignment module includes:

an update module configured to update a flow table entry associated with said destination vector responsive to a positive determination by said determination module;

a second update module configured to create a flow table entry associated with said destination vector and said one multicast virtual output queue responsive to a negative determination by said determination module.

47. The apparatus of claim 45 further including:

an update module configured to update said basis vector associated with said one multicast virtual output queue.

48. The apparatus of claim 45 wherein said update module is further configured to replace said basis vector with the centroid of said basis vector and said destination vector.

49. The apparatus of claim 45 wherein said update module further includes:

an adjustment module configured to adjust said basis vector by an amount calculated using a fixed centroid weight and said destination vector.

50. An apparatus having at least one processor and at least one memory coupled to said at least one processor for operating a switching device, said switching device having an input interface, said input interface having multicast capability, said apparatus comprising:

a set of multicast virtual output queues for said input interface;

a choose module configured to choose a set of basis vectors;

an association module configured to associate each basis vector of said set of basis vectors with a multicast virtual output queue of said set of multicast virtual output queues, responsive to said choose module;

a reception module configured to receive messages at said input interface; and

a queue module configured to queue said messages in a multicast virtual output queue of said set of multicast virtual output queues.

51. The apparatus of claim 50 wherein said choose module is configured to choose such that the sum of a distance measure between said set of basis vectors and a set of destination vectors is minimized.

52. The apparatus of claim 50 wherein one of said basis vectors is a broadcast vector.

53. The apparatus of claim 50 wherein said choose module is configured to choose using vector quantization.

54. A computer program product comprising:

a computer usable storage medium having computer readable code embodied therein for causing a computer to route a packet arriving at a switching device, said packet being associated with a set of destinations, said computer readable code includes;

computer readable code configured to receive a multicast message at an input interface, where said multicast message has an associated destination vector;

computer readable code configured to associate a basis vector with each multicast virtual output queue of a set of multicast virtual output queues said set of multicast virtual output queues having more than one and less than 2^N individual multicast virtual output queues for said input interface, where N equals the number of individual output interfaces to which the said multicast message could be directed;

computer readable code configured to select a basis vector, as a selected basis vector, by comparing said destination vector of said multicast message with each said basis vector; and

computer readable code configured to assign said multicast message to a multicast virtual output queue associated with said selected basis vector.

55. The computer program product of claim 54 wherein said comparing involves determining a distance measure between said destination vector and each said basis vector.

56. The computer program product of claim 55 wherein said distance measure is a square of a Euclidean distance.

57. A computer program of claim 54 further comprising:

computer readable code configured to send a head element of a multicast virtual output queue of said set of multicast virtual output queues to output interfaces.

58. A computer program product comprising:

a computer usable storage medium having computer readable code embodied therein for operating a switching device, said switching device having an input interface, said input interface having multicast capability, said input interface having a set of multicast virtual output queues, said computer readable code includes;

computer readable code configured to choose a set of basis vectors;

computer readable code configured to associate each basis vector of said set of basis vectors with a multicast virtual output queue of said set of multicast virtual output queues;

computer readable code configured to receive messages at said input interface; and

computer readable code configured to queue said messages in a multicast virtual output queue of said set of multicast virtual output queues.

59. A computer program product comprising:

a computer data signal embodied in a carrier wave having computer readable code embodied therein for causing a computer to route a packet arriving at a switching device, said packet being associated with a set of destinations, said computer readable code includes;

computer readable code configured to receive a multicast message at an input interface, where said multicast message has an associated destination vector;

computer readable code configured to associate a basis vector with each multicast virtual output queue of a set of multicast virtual output queues said set of multicast virtual output queues having more than one and less than 2^N individual multicast virtual output queues for said input interface, where N equals the number of individual output interfaces to which the said multicast message could be directed;

computer readable code configured to select a basis vector, as a selected basis vector, by comparing said destination vector of said multicast message with each said basis vector; and

computer readable code configured to assign said multicast message to a multicast virtual output queue associated with said selected basis vector.

60. A computer product of claim 59 further including:

computer readable code configured to send a head element of a multicast virtual output queue of said set of multicast virtual output queues to output interfaces.

61. A switching device, comprising:

means for receiving a multicast message at an input interface, where said multicast message has an associated destination vector;

means for associating a basis vector with each multicast virtual output queue of a set of multicast virtual output queues, said set of multicast virtual output queues having more than one and less than 2^N individual multicast virtual output queues for said input interface, where N equals the number of individual output interfaces to which the said multicast message could be directed;

means for selecting a basis vector, as a selected basis vector, by comparing said destination vector of said multicast message with each said basis vector; and

assigning said multicast message to a multicast virtual output queue associated with said selected basis vector.

62. A switching device as in claim 61 further comprising:

means for sending a head element of a multicast virtual output queue of said set of multicast virtual output queues to output interfaces.

63. A switching device as in claim 61 further comprising:

means for determining a distance measure between said destination vector and each said basis vector in said comparing said destination vector with each said basis vector.

64. A switching device as in claim 63 further comprising:

means for computing said distance measure as a square of a Euclidean distance.

65. A switching device as in claim 63 further comprising:

means for calculating said distance measure for destination vector {right arrow over (D)} and basis vector {right arrow over (B)} where both are of N dimensions, as $\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(d_i-b_i\right)}^2.$

66. A switching device as in claim 63 further comprising:

means for calculating said distance measure using a content addressable memory.

67. A switching device as in claim 61 further comprising:

means for computing an updated basis vector in response to said destination vector of said multicast message.

68. A switching device as in claim 67 further comprising:

means for computing said updated basis vector by the expression $\stackrel{\to <br><br>}{\mathrm{UB}}=\frac{\left[\stackrel{\to <br><br>}{\mathrm{SB}}+\left(\stackrel{\to <br><br>}{D}*\mathrm{CW}\right)\right]}{\left(1+\mathrm{CW}\right)}$

where {right arrow over (UB)} is said updated basis vector, {right arrow over (SB)} is said selected basis vector, {right arrow over (D)} is said destination vector, and CW is a centroid weight.

69. A switching device as in claim 68 further comprising:

means for setting CW=0.1.

70. A switching device as in claim 68 further comprising:

means for setting CW equal the centroid of said selected basis vector and said destination vector.

71. A switching device as in claim 68 further comprising:

means for saving updated basis vectors in memory; and

means for substituting said updated basis vectors for use as basis vectors in response to expiration of a window count.

72. A switching device, comprising:

means for receiving a packet at a multicast input interface of a switching device, said packet having an associated destination vector;

means for associating a basis vector with each multicast virtual output queue of a set of multicast virtual output queues to create a set of basis vectors;

means for selecting a multicast virtual output queue responsive to a comparison of said destination vector with said set of basis vectors, and

means for queuing said packet in said multicast virtual output queue.

73. A switching device as in claim 72 further comprising:

means for sending a head element of a multicast virtual output queue of said set of multicast virtual output queues to output interfaces.

74. A switching device as in claim 72 further comprising:

means for determining a distance measure between said destination vector and each said basis vector in said comparing said destination vector with each said basis vector.

75. A switching device as in claim 74 further comprising:

means for computing said distance measure as a square of a Euclidean distance.

76. A switching device as in claim 74 further comprising:

means for calculating said distance measure for destination vector {right arrow over (D)} and basis vector {right arrow over (B)} where both are of N dimensions, as $\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(d_i-b_i\right)}^2.$

77. A switching device as in claim 74 further comprising:

means for calculating said distance measure using a content addressable memory.

78. A switching device as in claim 72 further comprising:

means for computing an updated basis vector in response to said destination vector of said multicast message.

79. A switching device as in claim 78 further comprising:

means for computing said updated basis vector by the expression $\stackrel{\to <br><br>}{\mathrm{UB}}=\frac{\left[\stackrel{\to <br><br>}{\mathrm{SB}}+\left(\stackrel{\to <br><br>}{D}*\mathrm{CW}\right)\right]}{\left(1+\mathrm{CW}\right)}$

where {right arrow over (UB)} is said updated basis vector, {right arrow over (SB)} is said selected basis vector, {right arrow over (D)} is said destination vector, and CW is a centroid weight.

80. A switching device as in claim 79 further comprising:

means for setting CW=0.1.

81. A switching device as in claim 79 further comprising:

means for setting CW equal the centroid of said selected basis vector and said destination vector.

82. A switching device as in claim 78 further comprising:

means for saving updated basis vectors in memory, and means for substituting said updated basis vectors for use as basis vectors in response to expiration of a window count.