System and method for providing a bit indexed service chain

• US 10,225,187 B2
• Filed: 03/22/2017
• Issued: 03/05/2019
• Est. Priority Date: 03/22/2017
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Pfister, Pierre, Townsley, Mark, Desmouceaux, Yoann
• Primary Examiner(s): Park, Jung H
• Application Number:
  US15/465,764
• Publication Number:
  US 20180278521A1
• Time in Patent Office: 713 Days
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Disclosed is a method that modifies a bit indexed explicit replication (BIER) algorithm. The method includes receiving a packet at a node, wherein the packet includes a BIER header identifying a bitstring, the bitstring including a first bit indicating a first destination and a second bit indicating a second destination and forwarding the packet through one or more networks toward the first destination and the second destination based on the bitstring and a predetermined bit selection order. The predetermined bit selection order causes a sequential delivery of the packet to the first destination and the second destination. After the packet arrives at the first destination, the method includes setting the first bit to zero in the bitstring and forwarding the packet through the one or more networks toward the second destination according to the updated bitstring.

Claims

1. A method comprising:

receiving a packet at a node, wherein the packet comprises a bit indexed explicit replication (BIER) header identifying a bitstring, the bitstring comprising a plurality of bits each of which indicates a destination;

ANDing, in response to the receiving, the bitstring of the packet with a bitstring of a forwarding table of the node to yield a new bitstring, the new bitstring comprising at least a first bit indicating a first destination and a second bit indicating a second destination, the first bit and the second bit corresponding to respective bit positions associated with the first destination and the second destination;

forwarding the packet through one or more networks toward the first destination and the second destination based on the bitstring and a predetermined bit selection order, wherein the predetermined bit selection order and the bitstring yield a sequential delivery of the packet to the first destination and the second destination;

after the packet arrives at the first destination, setting the first bit to zero in the new bitstring to yield an updated bitstring;

ANDing, in response to the packet arriving at the first destination, the bitstring of the packet with a bitstring of a forwarding table of the first destination to yield a new updated bitstring; and

forwarding the packet through the one or more networks toward the second destination according to the new updated bitstring and the predetermined bit selection order.

2. The method of claim 1, wherein the predetermined bit selection order is based on a bit operation.

3. The method of claim 2, wherein the bit operation comprises one of find first set, count trailing zeros, or number of trailing zeros.

4. The method of claim 2, wherein the bit operation is based on one of an in-order scheme, a shortest path scheme, or a pseudo-random scheme.

5. The method of claim 1, wherein selecting the first bit comprises selecting a destination bit in the bitstring based on load-balancing.

6. The method of claim 1, further comprising forwarding the packet to the network in parallel according to a bit indexed explicit replication algorithm.

7. A system comprising:

at least one processor; and

a computer-readable storage device storing instructions which, when executed by the at least one processor, cause the at least one processor to perform operations comprising;

receiving a packet at a node, wherein the packet comprises a bit indexed explicit replication (BIER) header identifying a bitstring, the bitstring comprising a plurality of bits each of which indicates a destination;

ANDing, in response to the receiving, the bitstring of the packet with a bitstring of a forwarding table of the node to yield a new bitstring, the new bitstring comprising at least a first bit indicating a first destination and a second bit indicating a second destination, the first bit and the second bit corresponding to respective bit positions associated with the first destination and the second destination;

forwarding the packet through one or more networks toward the first destination and the second destination based on the bitstring and a predetermined bit selection order, wherein the predetermined bit selection order and the bitstring yield a sequential delivery of the packet to the first destination and the second destination;

after the packet arrives at the first destination, setting the first bit to zero in the new bitstring to yield an updated bitstring;

ANDing, in response to the packet arriving at the first destination, the bitstring of the packet with a bitstring of a forwarding table of the first destination to yield a new updated bitstring; and

forwarding the packet through the one or more networks toward the second destination according to the new updated bitstring and the predetermined bit selection order.

8. The system of claim 7, wherein the predetermined bit selection order is based on a bit operation.

9. The system of claim 8, wherein the bit operation comprises one of find first set, count trailing zeros, or number of trailing zeros.

10. The system of claim 8, wherein the bit operation is based on one of an in-order scheme, a shortest path scheme, or a pseudo-random scheme.

11. The system of claim 7, wherein selecting the first bit comprises selecting a destination bit in the bitstring based on load-balancing.

12. The system of claim 7, wherein the computer-readable storage device stores additional instructions which, when executed by the at least one processor, cause the at least one processor to perform operations further comprising:

forwarding the packet to the network in parallel according to a bit indexed explicit replication algorithm.

13. A non-transitory computer-readable storage device storing instructions which, when executed by at least one processor, cause the at least one processor to perform operations comprising:

receiving a packet at a node, wherein the packet comprises a bit indexed explicit replication (BIER) header identifying a bitstring, the bitstring comprising a plurality of bits each of which indicates a destination;

ANDing, in response to the receiving, the bitstring of the racket with a bitstring of a forwarding table of the node to yield a new bitstring, the new bitstring comprising at least a first bit indicating a first destination and a second bit indicating a second destination, the first bit and the second bit corresponding to respective bit positions associated with the first destination and the second destination;

forwarding the packet through one or more networks toward the first destination and the second destination based on the bitstring and a predetermined bit selection order, wherein the predetermined bit selection order and the bitstring yield a sequential delivery of the packet to the first destination and the second destination;

after the packet arrives at the first destination, setting the first bit to zero in the new bitstring to yield an updated bitstring;

ANDing, in response to the packet arriving at the first destination, the bitstring of the packet with a bitstring of a forwarding table of the first destination to yield a new updated bitstring; and

forwarding the packet through the one or more networks toward the second destination according to the new updated bitstring and the predetermined bit selection order.

14. The non-transitory computer-readable storage device of claim 13, wherein the predetermined bit selection order is based on a bit operation.

15. The non-transitory computer-readable storage device of claim 14, wherein the bit operation comprises one of find first set, count trailing zeros, or number of trailing zeros.