Deadlock-resistant fabric tree replication in a network device

Patent metadata

Field	Value
Publication number	US-9319347-B1
Application number	US-201514814820-A
Country	US
Kind code	B1
Filing date	Jul 31, 2015
Priority date	Dec 10, 2009
Publication date	Apr 19, 2016
Grant date	Apr 19, 2016

Abstract

In general, the invention is directed to techniques for reducing deadlocks that may arise when performing fabric replication. For example, as described herein, a network device includes packet replicators that each comprises a plurality of resource partitions. A replication data structure for a packet received by the network device includes packet replicator nodes that are arranged hierarchically to occupy one or more levels of the replication data structure. Each of the resource partitions in each of the plurality of packet replicators is associated with a different level of the replication data structure. The packet replicators replicate the packet according to the replication data structure, and each of the packet replicators handles the packet using the one of the resource partitions of the packet replicator that is associated with the level of the replication data structure occupied by the node that corresponds to that particular packet replicator.

First claim

What is claimed is:

1. A method comprising:
configuring, by a network device for each packet replicator of a plurality of packet replicators of the network device, a plurality of partitions of a packet buffer of the packet replicator to store multicast packet data received by the network device;
generating, by the network device, a plurality of multi-level replication data structures each having nodes hierarchically arranged in a plurality of levels that define an internal forwarding relationship among the nodes, wherein each node represents one of the plurality of packet replicators;
generating, by the network device from the plurality of multi-level replication data structures, forwarding information that maps the plurality of levels of each of the plurality of multi-level replication data structures to respective partitions of the plurality of partitions of packet buffers of the plurality of packet replicators; and
internally forwarding, by the plurality of packet replicators according to the forwarding information, the multicast packet data received by the network device.

2. The method of claim 1 , further comprising:
associating, for each packet replicator of the plurality of packet replicators, partitions of the plurality of partitions of the packet buffer of the packet replicator with respective multicast virtual interfaces of a plurality of multicast virtual interfaces for the packet replicator.

3. The method of claim 2 , further comprising:
storing, by each packet replicator of the plurality of packet replicators, multicast packet data, received by the packet replicator at a multicast virtual interface of the plurality of multicast virtual interfaces, to the partition of the packet buffer of the packet replicator that is associated with the multicast virtual interface.

4. The method of claim 2 , further comprising:
receiving, by a first packet replicator of the plurality of packet replicators from a second packet replicator of the plurality of packet replicators and for first data of the multicast packet data, an interface access request that identifies a first multicast virtual interface of the plurality of multicast virtual interfaces for the first packet replicator; and
sending, by the first packet replicator to the second packet replicator and only in response to determining the partition of the packet buffer of the first packet replicator that is associated with the first multicast virtual interface has sufficient buffering capacity for the first data, an access grant notification for the interface access request.

5. The method of claim 1 , wherein each of the plurality of multi-level replication data structures is associated with a different multicast group address.

6. The method of claim 1 , wherein each packet replicator of the plurality of packet replicators comprises a packet forwarding engine.

7. The method of claim 1 ,
wherein a first packet replicator of the plurality of packet replicators is represented by a root of a first multi-level replication data structure of the plurality of multi-level replication data structures, and
wherein a second packet replicator of the plurality of packet replicators, different from the first packet replicator, is represented by a root of a second multi-level replication data structure of the plurality of multi-level replication data structures that is different from the first multi-level replication data structure.

8. The method of claim 7 , wherein internally forwarding, according to the forwarding information, the multicast packet data received by the network device comprises,
internally forwarding, by the first packet replicator, first data of the multicast forwarding data to the second packet replicator according to first forwarding information of the forwarding information, the first forwarding information generated from the first multi-level replication data structure, and
internally forwarding, by the second packet replicator, second data of the multicast forwarding data to the first packet replicator according to second forwarding information of the forwarding information, the second forwarding information generated from the second multi-level replication data structure.

9. A network device comprising:
a plurality of packet replicators interconnected by a switch fabric, wherein each packet replicator of the plurality of packet replicators is configured with a plurality of partitions of a packet buffer of the packet replicator to store multicast packet data received by the network device;
at least one processor configured to generate a plurality of multi-level replication data structures each having nodes hierarchically arranged in a plurality of levels that define an internal forwarding relationship among the nodes, wherein each node represents one of the plurality of packet replicators,
wherein the at least one processor is further configured to generate, from the plurality of multi-level replication data structures, forwarding information that maps the plurality of levels of each of the plurality of multi-level replication data structures to respective partitions of the plurality of partitions of packet buffers of the plurality of packet replicators, and
wherein the plurality of packet replicators are configured to internally forward, according to the forwarding information, the multicast packet data received by the network device.

10. The network device of claim 9 , wherein each packet replicator of the plurality of packet replicators is configured with an association of partitions of the plurality of partitions of the packet buffer of the packet replicator with respective multicast virtual interfaces of a plurality of multicast virtual interfaces for the packet replicator.

11. The network device of claim 10 , wherein each packet replicator of the plurality of packet replicators is configured to store multicast packet data, received by the packet replicator at a multicast virtual interface of the plurality of multicast virtual interfaces, to the partition of the packet buffer of the packet replicator that is associated with the multicast virtual interface.

12. The network device of claim 10 ,
wherein a first packet replicator of the plurality of packet replicators is configured to receive, from a second packet replicator of the plurality of packet replicators and for first data of the multicast packet data, an interface access request that identifies a first multicast virtual interface of the plurality of multicast virtual interfaces for the first packet replicator, and
wherein the first packet replicator is configured to send, to the second packet replicator and only in response to determining the partition of the packet buffer of the first packet replicator that is associated with the first multicast virtual interface has sufficient buffering capacity for the first data, an access grant notification for the interface access request.

13. The network device of claim 9 , wherein each of the plurality of multi-level replication data structures is associated with a different multicast group address.

14. The network device of claim 9 , wherein each packet replicator of the plurality of packet replicators comprises a packet forwarding engine.

15. The network device of claim 9 ,
wherein a first packet replicator of the plurality of packet replicators is represented by a root of a first multi-level replication data structure of the plurality of multi-level replication data structures, and
wherein a second packet replicator of the plurality of packet replicators, different from the first packet replicator, is represented by a root of a second

Assignees

• Juniper Networks Inc

Inventors

• Sindhu Pradeep
• Frailong Jean-Marc
• Thomas Sarin
• Vegesna Srihari Raju
• Ofelt David James
• Wu Chang-Hong

Classifications

• H04L49/90

  Buffering arrangements · CPC title

• H04L49/201 Primary

  Multicast operation; Broadcast operation · CPC title

• H04L67/1095 Primary

  Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes · CPC title

• H04L45/16

  Multipoint routing · CPC title

• H04L12/18

  for broadcast or conference {, e.g. multicast} · CPC title