Deterministic and optimized bit index explicit replication (bier) forwarding

Patent metadata

Field	Value
Publication number	US-2016134535-A1
Application number	US-201414534689-A
Country	US
Kind code	A1
Filing date	Nov 6, 2014
Priority date	Nov 6, 2014
Publication date	May 12, 2016
Grant date	—

Abstract

A network device creates multiple forwarding tables, and each forwarding table includes information associated with a first set of destinations and a second set of destinations. The first set of destinations is different than the second set of destinations. The network device determines, for each forwarding table, next hops for the first set of destinations, and determines, for each forwarding table, equal cost multipath next hops for the second set of destinations. The network device populates the multiple forwarding tables with information associated with the next hops and the equal cost multipath next hops, and the multiple forwarding tables are used to forward a multicast packet toward multiple destinations.

First claim

What is claimed is:

1 . A network device, comprising:
one or more processors to:
create a plurality of forwarding tables,
each of the plurality of forwarding tables including information associated with a first set of destinations and a second set of destinations, the first set of destinations being different than the second set of destinations;

determine, for each of the plurality of forwarding tables, next hops for the first set of destinations;
determine, for each of the plurality of forwarding tables, equal cost multipath next hops for the second set of destinations; and
populate the plurality of forwarding tables with information associated with the next hops and the equal cost multipath next hops,
one or more of the plurality of forwarding tables being used to forward a multicast packet toward a plurality of destinations.

2 . The network device of claim 1 , where the one or more processors are further to:
store the plurality of forwarding tables; and program the plurality of forwarding tables into a data plane used to forward multicast packets.

3 . The network device of claim 1 , where each of the plurality of forwarding tables includes a single possible next hop for each destination of the first set of destinations or the second set of destinations.

4 . The network device of claim 1 , where the plurality of forwarding tables include a plurality of bit index forwarding tables (BIFTs).

5 . The network device of claim 1 , where, when determining, for each of the plurality of forwarding tables, the equal cost multipath next hops for the second set of destinations, the one or more processors are further to:
utilize a heuristic method to determine, for each of the plurality of forwarding tables, the equal cost multipath next hops for the second set of destinations, based on the next hops for the first set of destinations.

6 . The network device of claim 1 , where the one or more processors are further to:
receive the multicast packet that includes information identifying destination addresses for the multicast packet; analyze the multicast packet to determine a particular forwarding table, of the plurality of forwarding tables, to use for the multicast packet; identify particular next hops associated with the particular forwarding table and associated with the destination addresses; and forward the multicast packet to the particular next hops,
the particular next hops forwarding the multicast packet toward destinations associated with the destination addresses.

7 . The network device of claim 6 , where, when analyzing the multicast packet, the one or more processors are further to:
apply a hash function to at least a portion of the multicast packet to determine the particular forwarding table, of the plurality of forwarding tables, to use for the multicast packet.

8 . The network device of claim 6 , where, when forwarding the multicast packet to the particular next hops, the one or more processors are further to:
create a copy of the multicast packet for each of the particular next hops; and forward the copy of the multicast packet to each of the particular next hops.

9 . A method, comprising:
creating, by a network device provided in a network, a plurality of forwarding tables,
each of the plurality of forwarding tables including information associated with a first set of destinations and a second set of destinations, the first set of destinations being different than the second set of destinations;
determining, by the network device and for each of the plurality of forwarding tables, next hops for the first set of destinations; determining, by the network device and for each of the plurality of forwarding tables, equal cost multipath next hops for the second set of destinations; and populating, by the network device, the plurality of forwarding tables with information associated with the next hops and the equal cost multipath next hops,
one or more of the plurality of forwarding tables being used to forward a multicast packet toward a plurality of destinations.

10 . The method of claim 9 , further comprising:
programming the plurality of forwarding tables into a data plane associated with the network device and used to forward multicast packets.

11 . The method of claim 9 , where each of the plurality of forwarding tables includes a single possible next hop for each destination of the first set of destinations or the second set of destinations.

12 . The method of claim 9 , where a heuristic method and the first equal cost multipath next hops are utilized for determining, for each of the plurality of forwarding tables, the equal cost multipath next hops for the second set of destinations.

13 . The method of claim 9 , further comprising:
receiving the multicast packet that includes information identifying destination addresses for the multicast packet; analyzing the multicast packet to determine a particular forwarding table, of the plurality of forwarding tables, to use for the multicast packet; identifying particular next hops associated with the particular forwarding table and associated with the destination addresses; and forwarding the multicast packet to the particular next hops,
the particular next hops forwarding the multicast packet toward destinations associated with the destination addresses.

14 . The method of claim 13 , where a hash function is applied to one or more fields of a header of the multicast packet for determining the particular forwarding table, of the plurality of forwarding tables, to use for the multicast packet.

15 . The method of claim 13 , where forwarding the multicast packet to the particular next hops further comprises:
creating a copy of the multicast packet for each of the particular next hops; and forwarding the copy of the multicast packet to each of the particular next hops.

16 . A bit-forwarding device, comprising:
one or more processors to:
receive a multicast packet that includes information identifying destination addresses for the multicast packet;
analyze the multicast packet to determine a particular bit index forwarding table, of a plurality of bit index forwarding tables, to use for the multicast packet;
identify particular equal cost multipath next hops associated with the particular bit index forwarding table and associated with the destination addresses; and
forward the multicast packet to the particular equal cost multipath next hops,
the particular equal cost multipath next hops forwarding the multicast packet toward destinations associated with the destination addresses.

17 . The bit-forwarding device of claim 16 , where, when forwarding the multicast packet to the particular equal cost multipath next hops, the one or more processors are further to:
create a copy of the multicast packet for each of the particular equal cost multipath next hops; and forward the copy of the multicast packet to each of the particular equal cost multipath next hops.

18 . The bit-forwarding device of claim 16 , where, prior to receiving the multicast packet, the one or more processors are further to:
create the plurality of bit index forwarding tables
each of the plurality of forwarding tables including information associated with a first set of destinations and a second set of destinations, the first set of destinations being different than the second set of destinations;
determine, for each of the plurality of bit index forwarding tables, next hops for the first set of destinations; determine, for each of the

Assignees

• Juniper Networks Inc

Inventors

• Callon Ross

Classifications

• H04L45/24

  Multipath · CPC title

• H04L12/1881

  with schedule organisation, e.g. priority, sequence management · CPC title

• H04L45/16

  Multipoint routing · CPC title

• H04L45/7453 Primary

  using hashing · CPC title

• H04L45/74 Primary

  Address processing for routing · CPC title