System and method to control latency of serially-replicated multi-destination flows

• US 10,218,525 B2
• Filed: 11/11/2016
• Issued: 02/26/2019
• Est. Priority Date: 11/11/2016
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Nguyen, Dennis Khoa Dang, Huang, Chih-Tsung
• Primary Examiner(s): Pancholi, Rina C
• Application Number:
  US15/349,629
• Publication Number:
  US 20180139066A1
• Time in Patent Office: 837 Days
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers

Abstract

Exemplified systems and methods facilitate multicasting latency optimization operations for router, switches, and other network devices, for routed Layer-3 multicast packets to provide even distribution latency and/or selective prioritized distribution of latency among multicast destinations. A list of network destinations for serially-replicated packets is traversed in different sequences from one packet to the next, to provide delay fairness among the listed destinations. The list of network destinations are mapped to physical network ports, virtual ports, or logical ports of the router, switches, or other network devices and, thus, the different sequences are also traversed from these physical network ports, virtual ports, or logical ports. The exemplified systems and methods facilitates the management of traffic that is particularly beneficial in in a data center.

Claims

1. An apparatus comprising a plurality of network ports configured to serially replicate multicast traffic, the multicast traffic including a first multicast traffic and a second multicast traffic so as to forward, via a network, replicated multicast traffic to a plurality of computing devices, wherein each multicast traffic comprises one or more packets to be directed to multiple destination flows, the apparatus comprising:

a Multicast Expansion Table (MET), implemented in memory of the apparatus, comprising a plurality of entries, wherein at least two of the plurality of entries comprise two or more pointers that form groups of pointers, including a first group and a second group, wherein each group of the first group and second group includes a set of pointers that form a multi-linked list associated with traversal of the plurality of entries, and wherein each of the at least two entries is associated with one or more network ports of the plurality of network ports, and wherein traversal of a group of pointers associated with the plurality of entries, or a portion thereof, of the Multicast Expansion Table, for a given multicast traffic, defines a sequence of the serial replication of the given multicast traffic over one or more sets of network ports; and

a network interlace, wherein the network interface is configured to i) serially replicate packets associated with the first multicast traffic over a first set of network ports in accordance with a first sequence corresponding to a first traversal of the entries in the Multicast Expansion Table when the first group is selected, and ii) serially replicate packets associated with the second multicast traffic in accordance with a second sequence corresponding to a second traversal of the entries of the Multicast Expansion Table when the second group is selected, wherein the first sequence is different from the second sequence.

3. The apparatus of claim 1, wherein each entry of the plurality of entries of the Multicast Expansion Table comprises the two one or more pointers, each pointer addressing a next entry in the plurality of entries to form a traversable sequence for the first multicast traffic and the second multicast traffic.

4. The apparatus of claim 1, wherein each entry of the plurality of, entries of the Multicast Expansion Table comprises two or more pointers, each pointer of a given entry addressing a next entry in the plurality of entries to form a single traversable sequence for the first multicast traffic and the second multicast traffic, the two or more pointers, collectively, forming multiple traversable sequences, including a first traversable sequence associated with a first pointer in the given entry and a second traversable sequence associated with a second pointer in the given entry.

5. The apparatus of claim 1, wherein the Multicast Expansion Table comprises an identifier for each entry, the apparatus comprising a second Multicast Expansion Table comprising a plurality of pointers that each addresses the identifier for the each entry to form a given traversable sequence for the first multicast traffic and the second multicast traffic.

6. The apparatus of claim 1, wherein each entry of the plurality of entries of the Multicast Expansion Table comprises the two or more pointers, each pointer addressing a next entry in the plurality of entries to form a given traversable sequence for the first multicast traffic and the second multicast traffic, the apparatus comprising:

a processor; and

the memory, wherein the memory comprises instructions stored thereon, wherein execution of the instructions, cause the processor to;

generate the two or more pointers for the Multicast Expansion Table, wherein the two or more pointers are generated according to an order selected from the group consisting of a random order, a numerical order, and a reverse numerical order.

7. The apparatus of claim 1, wherein each entry of the plurality of entries of the Multicast Expansion Table comprises the two or more pointers, each pointer addressing a next entry in the plurality of entries to form a given traversable sequence for the first multicast traffic, the apparatus comprising:

a processor; and

the memory, wherein the memory comprises instructions stored thereon, wherein execution of the instructions, cause the processor to;

generate the two of more pointers for the Multicast Expansion Table, wherein the two or more pointers are generated according to a priority value associated with the first multicast traffic.

8. The apparatus of claim 1, wherein each entry of the plurality of entries of the Multicast Expansion Table comprises the two or more pointers, each pointer addressing a next entry in the plurality of entries to form a given traversable sequence for the first multicast traffic and the second multicast traffic, the apparatus comprising:

a processor; and

the memory, wherein the memory comprises instructions stored thereon, wherein execution of the instructions, cause the processor to;

update, upon each replication of the first multicast traffic and the second multicast traffic, an average latency value for each network port of the plurality of network ports; and

generate the two or more pointers for the Multicast Expansion Table, wherein the two or more pointers are generated according to a largest serially replicated flow delay value of the average latency value to a lowest value of the average latency value.

9. The apparatus of claim 1, wherein the Multicast Expansion Table comprises an identifier for each entry, the apparatus comprising a second Table comprising a plurality of pointers that each addresses the identifier for each entry to form a given traversable sequence for the first multicast traffic and the second multicast traffic, the apparatus comprising:

a processor; and

the memory, wherein the memory comprises instructions stored thereon, wherein execution of the instructions, cause the processor to;

generate the plurality of pointers for the Multicast Expansion Table, wherein the plurality of pointers are generated according to an order selected from the group consisting of a random order, a numerical order, and a reverse numerical order.

10. The apparatus of claim 1, wherein the Multicast Expansion Table comprises an identifier for each entry, the apparatus comprising a second Table comprising a plurality of pointers that each addresses the identifier for each entry to form a given traversable sequence for the first multicast traffic and the second multicast traffic, the apparatus comprising:

a processor; and

the memory, wherein the memory comprises instructions stored thereon, wherein execution of the instructions, cause the processor to;

generate the plurality of pointers for the Multicast Expansion Table, wherein the plurality of pointers are generated according to a priority value associated with a given multicast traffic.

11. The apparatus of claim 1, wherein the Multicast Expansion Table comprises an identifier for each entry, the apparatus comprising a second Table comprising a plurality of pointers that each addresses the identifier for each entry to form a given traversable sequence for a given multicast traffic, the apparatus comprising:

a processor; and

the memory, wherein the memory comprises instructions stored thereon, wherein execution of the instructions, cause the processor to;

update, upon each replication of a given multicast traffic, an average latency value for each network port of the plurality of network ports; and

generate the pointers for the Multicast Expansion Table, wherein the plurality of pointers are generated according to a largest serially replicated flow delay value of the average latency value to a lowest value of the average latency value.

12. The apparatus of claim 1, wherein all packets in a flow or a burst of flow associated with the first multicast traffic are serially replicated across the plurality of network ports according to the first sequence prior to packets in a second flow or second burst of flow associated with the second multicast traffic being serially replicated across the plurality of network ports according to the second sequence.

13. The apparatus of claim 1, wherein multicast traffic are serially replicated according to a plurality of sequences, each consecutive sequence differing from the previous sequence so as to vary sequence of packets replication across the plurality of network ports, the apparatus comprising:

a processor; and

the memory, the memory having instructions stored thereon, wherein execution of the instructions, cause the processor to;

measure packet latency parameters for the plurality of network ports; and

generate a current sequence or a next sequence of packet replication over the plurality of network ports based on the measured packet latency parameters.

14. The apparatus of claim 1, wherein multicast traffic are serially replicated according to a plurality of sequences, each consecutive sequence differing from the previous sequence so as to vary a sequence of packets replication across the plurality of network ports, the apparatus comprising:

a processor; and

the memory, the memory having instructions stored thereon, wherein execution of the instructions, cause the processor to;

maintain an identifier associated with a set of network ports that is latency-sensitive; and

generate a current sequence or a next sequence of packet replication over the plurality of network ports based on the maintained identifier such that the set of network ports that is latency-sensitive is located proximal to a beginning portion of the current or next sequence.

15. The apparatus of claim 1, comprising:

a processor; and

the memory, the memory having instructions stored thereon, wherein execution of the instructions, cause the processor to;

cause a received multicast traffic to be serially replicated across the plurality of network ports, wherein packets associated with the replicated multicast traffic are each encapsulated with a header field that comprises field data associated with the MET Traversal Sequence (MTS).

16. The apparatus of claim 15, wherein, the first multicast traffic and the second multicast traffic comprise a same n-tuple.

17. The apparatus of claim 1,

wherein each entry of the plurality of entries of the Multicast Expansion Table comprises two or more pointers, each pointer of a given entry addressing a next entry in the plurality of entries to form a single traversable sequence for a given multicast traffic, the two or more pointers, collectively, forming multiple traversable sequence, including a first traversable sequence associated with a first pointer in the given entry and a second traversable sequence associated with a second pointer in the given entry, the apparatus comprising:

a processor; and

the memory, the memory having instructions stored thereon, wherein execution of the instructions, cause the processor to;

transmit a message to a second apparatus or a controller in the network, the message comprising a parameter associated with a number of sequences available per apparatus for the two or more pointers, wherein the transmitted parameter causes the second apparatus to vary a sequence to serially replicate a given multicast traffic thereat.

18. The apparatus of claim 1, wherein the apparatus comprises a switch or a router.

2. The apparatus of dam 1, wherein packets associated with the first and second multicast traffic are serially replicated according to a plurality of sequences, each consecutive sequence differing from the previous sequence to vary a sequence of packets replication across the plurality of network ports, wherein each network port has a replication latency matching that of other ports.

19. A method comprising:

receiving, at a network port of a network device, a first packet associated with a first multicast traffic; and

in response to receipt of the first packet, i) serially replicating, across a first set of network ports of a plurality of network ports associated with the network device, according to a first sequence of the first set of network ports, the first multicast traffic and ii) forwarding, via a network, the replicated multicast traffic to a plurality of computing devices associated with the first multicast traffic;

receiving, at the network device, a second packet associated with a second multicast traffic; and

in response to receipt of the second packet, i) serially replicating, across a second set of network ports of a plurality of network ports associated with the network device, according to a second sequence of the second set of network ports, the second multicast traffic and ii) forwarding, via the network, the replicated multicast traffic to a plurality of computing devices associated with the second multicast traffic,

wherein the serial replication of the first multicast traffic and the second multicast traffic is i) based on traversal of a plurality of entries in a Multicast Expansion Table (MET) associated with the network device and ii) based on a sequence list associated therewith, each entry being associated with a network port of the first set of network ports, wherein the first sequence is different from the second sequence, wherein at least two of the plurality of entries comprise two or more pointers that form groups of pointers, including a first group and a second group, wherein each group of the first group and second group includes a set of pointers that form a multi-linked list associated with traversal of the plurality of entries, or the portion thereof, and wherein each of the at least two entries is associated with one or more network ports of the plurality of network ports.

20. A non-transitory computer readable medium comprising instructions stored thereon, wherein execution of the instructions, cause a processor a network device to cause the network device to:

in response to receiving, at a network port of the network device, a first packet associated with a first multicast traffic, i) serially replicate, across a first set of network ports of a plurality of network ports associated with the network device, according to a first sequence of the first set of network ports, the packets associated with the first multicast traffic and ii) forward, via a network, the replicated multicast traffic to a plurality of computing devices associated with the first multicast traffic; and

in response to receiving a second packet associated with a second multicast traffic, i) serially replicate, across a second set of network ports of a plurality of network ports associated with the network device, according to a second sequence of the second set of network ports, the second multicast traffic and ii) forward, via the network, the replicated multicast traffic to a plurality of computing devices associated with the second multicast traffic,

wherein the serial replication of the first multicast traffic and the second multicast traffic is i) based on traversal of a plurality of entries in a Multicast Expansion Table (MET) associated with the network device and ii) based on a sequence list associated therewith, each entry being associated with a network port of the first set of network ports, wherein the first sequence is different from the second sequence, wherein at least two of the plurality of entries comprise two or more pointers that form groups of pointers, including a first group and a second group, wherein each group of the first group and second group includes a set of pointers that form a multi-linked list associated with traversal of the plurality of entries, or the portion thereof.