System and method for providing a bit indexed service chain

Patent metadata

Field	Value
Publication number	US-10778576-B2
Application number	US-201916249563-A
Country	US
Kind code	B2
Filing date	Jan 16, 2019
Priority date	Mar 22, 2017
Publication date	Sep 15, 2020
Grant date	Sep 15, 2020

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.

First claim

What is claimed is:

1. A method comprising:
receiving a packet at a node, wherein the packet includes a bitstring having a plurality of bits each of which indicates a destination;
ANDing, in response to the receiving, the bitstring of the packet with a bitstring from 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;
first forwarding the packet toward the first destination and the second destination based on the new bitstring such that packet is delivered to the first destination before the second destination;
after the packet arrives at the first destination, changing 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 from the first destination to yield a new updated bitstring; and
second forwarding the packet toward the second destination according to the new updated bitstring.

2. The method of claim 1 , wherein the first forwarding is also based on predetermined bit selection order that 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 an in-order.

5. The method of claim 2 , wherein the bit operation is based on a shortest path scheme.

6. The method of claim 2 , wherein the bit operation is based on a pseudo-random scheme.

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

8. A system comprising:
at least one processor; and
a computer-readable memory 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 includes a bitstring having a plurality of bits each of which indicates a destination;
ANDing, in response to the receiving, the bitstring of the packet with a bitstring from 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;
first forwarding the packet toward the first destination and the second destination based on the new bitstring such that packet is delivered to the first destination before the second destination;
after the packet arrives at the first destination, changing 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 from the first destination to yield a new updated bitstring; and
second forwarding the packet toward the second destination according to the new updated bitstring.

9. The system of claim 8 , wherein the first forwarding is also based on predetermined bit selection order that is based on a bit operation.

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

11. The system of claim 9 , wherein the bit operation is based on an in-order scheme.

12. The system of claim 9 , wherein the bit operation is based on a shortest path scheme.

13. The system of claim 9 , wherein the bit operation is based on a pseudo-random scheme.

14. The system of claim 8 , the operations further comprising third forwarding the packet in parallel according to a bit indexed explicit replication algorithm.

15. A non-transitory computer-readable media 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 includes a bitstring having a plurality of bits each of which indicates a destination;
ANDing, in response to the receiving, the bitstring of the packet with a bitstring from 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;
first forwarding the packet toward the first destination and the second destination based on the new bitstring such that packet is delivered to the first destination before the second destination;
after the packet arrives at the first destination, changing 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 from the first destination to yield a new updated bitstring; and
second forwarding the packet toward the second destination according to the new updated bitstring.

16. The media of claim 15 , wherein the first forwarding is also based on predetermined bit selection order that is based on a bit operation.

17. The media of claim 16 , wherein the bit operation comprises one of find first set, count trailing zeros, or number of trailing zeros.

18. The media of claim 16 , wherein the bit operation is based on an in-order.

19. The media of claim 16 , wherein the bit operation is based on a shortest path scheme.

20. The media of claim 16 , wherein the bit operation is based on a pseudo-random scheme.

Assignees

• Cisco Tech Inc

Inventors

• Pfister Pierre
• Townsley Mark
• Desmouceaux Yoann

Classifications

• H04L45/74 Primary

  Address processing for routing · CPC title

• H04L69/22

  Parsing or analysis of headers · CPC title