Internet DRAFT - draft-zhang-bier-designed-routing
draft-zhang-bier-designed-routing
BIER WG Sandy. Zhang
Internet-Draft Bo. Wu
Intended status: Standards Track ZTE Corporation
Expires: May 4, 2016 November 1, 2015
Designed Routing in BIER Forwarding
draft-zhang-bier-designed-routing-01.txt
Abstract
BIER specifies a new architecture for the forwarding of multicast
data packets. As the [I-D.ietf-bier-architecture] said, in the BIER
domain, it does not require a protocol for explicitly building
multicast distributing trees, nor does it require intermediate nodes
to maintain any per-flow state. In some deployments, some specific
multicast flows may be forwarded by special routing; it cannot be
achieved by the forwarding rule that is provided. In this document
we will defined a new routing list in BIER header, the packets will
be steered according to the routing list.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on May 4, 2016.
Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
Zhang & Wu Expires May 4, 2016 [Page 1]
Internet-Draft Designed Routing in BIER Forwarding November 2015
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Designed Routing . . . . . . . . . . . . . . . . . . . . . . 3
2.1. The node's level . . . . . . . . . . . . . . . . . . . . 3
3. Format of designed routing list . . . . . . . . . . . . . . . 3
3.1. BitString . . . . . . . . . . . . . . . . . . . . . . . . 4
3.1.1. unified BSL . . . . . . . . . . . . . . . . . . . . . 4
3.1.2. Different BSL . . . . . . . . . . . . . . . . . . . . 5
4. Encapsulate the designed routing list . . . . . . . . . . . . 6
5. Decapsulate the packet . . . . . . . . . . . . . . . . . . . 7
6. Forwarding treatment . . . . . . . . . . . . . . . . . . . . 7
6.1. Process the designed routing list . . . . . . . . . . . . 8
7. Security Considerations . . . . . . . . . . . . . . . . . . . 13
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13
9. Normative References . . . . . . . . . . . . . . . . . . . . 13
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13
1. Introduction
As the [I-D.ietf-bier-architecture] described, BIER specifies a new
architecture for the forwarding of multicast data packets. And the
extension of OSPF/ISIS is used to flood the BIER information to
establish the BIER forwarding table. The calculation algorithm of
IGP is calculating the shortest path to every BIER node. It means
that the forwarding in BIER is along the shortest path.
--------- B ------ C --------
| | | |
A ------- D ------ E ------ F
| | | |
--------- G ------ H --------
Figure 1: An example of packets forwarding
For example, in figure 1, in the forwarding table of node A, here
supposes that the shortest path to node C is node B, the shortest
path to node H is node G. If there is one specific multicast flow
that should be forwarding to node C, node F and node H. Then the
forwarding path will be node A --- node B --- node C, node A--- node
D --- node E --- node F, node A --- node G --- node H. If we want to
merge the flows in one optimizing path of node A --- node D --- node
E --- node C/ node F/ node H, we cannot implement it due to the
shortest forwarding algorithm.
Zhang & Wu Expires May 4, 2016 [Page 2]
Internet-Draft Designed Routing in BIER Forwarding November 2015
This document specifies a way to forward multicast packets by
designed routing. These multicast packets are encapsulated by
specific header. The BIER nodes forward the packets by designed
routing that is carried in specific BIER header. In figure 1, node A
send the packets with designed routing list. The packets will be
forwarded by the nodes list in the designed routing list of node A
--- node D --- node E --- node C/ node F/ node H.
2. Designed Routing
The packets that are forwarded by BIER nodes are filled with designed
routing in the BIER header, which carries the nodes list in order.
The nodes are divided into differentiate levels that are classified
by the distance from the ingress node.
2.1. The node's level
------- B ------ D ------ F
|
A-------C ------ E
Figure 2
For example, in figure2, node A is ingress node, the node F and node
E are egress nodes. Node B and C are the first level nodes that one
specific multicast flow should be forwarded to, node D and E are the
second level nodes that the flow should be forwarded to. There is
only one node F in the third level.
3. Format of designed routing list
The designed routing list that is followed by the BIER header should
be distinguished by some specific flag in the BIER header. One of
the reserved bits may be used for the proposal. When the rightmost
bit of the reserved field is set to 1, it indicates that the designed
routing list is followed by the BIER header of the packet. As showed
below:
Zhang & Wu Expires May 4, 2016 [Page 3]
Internet-Draft Designed Routing in BIER Forwarding November 2015
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 1 0 1| Ver | Len | Entropy |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| BitString (first 32 bits) ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ BitString (last 32 bits) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|OAM| Reserved 1| Proto | BFIR-id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3
The designed routing list is comprised of a TLV, include type, length
and value. The type of TLV indicates the routing information and
form. There are many different types for the designed routing that
may have many various formats, which may be expressed by bitstring,
bfr-id list, or bfr-prefix list, and so on. The following section
defines how to use the bitstring to express the designed routing
list.
3.1. BitString
The BitPosition(BP) is used to indicate the nodes in BIER header.
And it can be used in the list of designed routing. It's flexible to
choose the corresponding BSL for packet's encapsulation. So it's
also flexible to encapsulate the list of designed routing. The
neighbor's format in the routing list should be used for two types.
3.1.1. unified BSL
Figure 4 illustrates using one unified BSL in the designed routing
list, which means all level nodes in the list share the same BSL.
Zhang & Wu Expires May 4, 2016 [Page 4]
Internet-Draft Designed Routing in BIER Forwarding November 2015
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Current level |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bit String Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| level | Bit String ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ Bit String |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| level | Bit String ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ Bit String |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4
o Type : TBD. Suggest type 1.
o Length: The length of this TLV.
o Current level: Indicate the recent level that should be processed
by the receiving node in the designed routing list. It will be
increased by 1 after the processing of nodes in the designed
routing.
o Bit String Length: Indicate the BSL that be used in the designed
routing list.
o Level: Indicate the node's level of the designed routing.
o Bit String: All the nodes in the same level should be encapsulated
in one bitstring.
3.1.2. Different BSL
Also different BSL should be used to express the nodes in the
designed routing list. As sketched in Figure 5, different level
nodes may be encapsulated in different BSL.
Zhang & Wu Expires May 4, 2016 [Page 5]
Internet-Draft Designed Routing in BIER Forwarding November 2015
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Current level |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| level | Bit String Length ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ | Bit String ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ Bit String |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| level | Bit String Length ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ | Bit String ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ Bit String |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 5
o Type : TBD. Suggest type 2.
o Length: The length of this TLV.
o Current level: Indicate the recent level that should be processed
by the receiving node in the designed routing list. It will be
increased by 1 after the processing of nodes in the designed
routing.
o Level: Indicate the node's level of the designed routing.
o Bit String Length: Indicate the BSL that be used in this level.
o Bit String: All the nodes in the same level do be encapsulated in
one bitstring.
4. Encapsulate the designed routing list
When the ingress node gathers all the egress nodes in the BIER
domain, it should encapsulate the BIER header as regular function
first when traffic arrives. If this traffic is classified to be
forwarded by one designed routing, the ingress node then encapsulates
the nodes' list in the designed routing list. The designed routing
list may be provided from the controller or the module of PCE, and so
on. The nodes in one same level should be encapsulated together.
Zhang & Wu Expires May 4, 2016 [Page 6]
Internet-Draft Designed Routing in BIER Forwarding November 2015
------- B ------ C ------ D
| |
A-------E ------ F
| |
------- G ------ H ----- K
Figure 6
For example, there are several nodes in one BIER domain. Suppose
that for one specific multicast flow, the ingress node is A, and the
egress nodes are D, F and K. The designed routing list is A-E-F-C-D,
A-E-F-H-K. What is more, node B is the shortest path next hop from A
to D, node G is the shortest path next hop from A to K.
The designed routing is divided into four levels, the first level
includes node E. The second level includes node F. The third level
includes node C and node H. The fourth level includes node D and
node K.
Node A encapsulates all the nodes in the path to the designed routing
list. The current level is set to 1.
5. Decapsulate the packet
When the packet is forwarded to one of the egress nodes, the egress
node will detect that it is one of the egress nodes due to the
bitstring in the BIER header. The egress nodes decapsulate the BIER
header and forward it to the previous domain by reductive format.
And if the egress node notices that there are still many nodes in the
designed routing list that should be forwarded, the egress node will
forward packets to next node due to the designed routing list.
6. Forwarding treatment
When the BIER nodes receive a packet that is encapsulated by BIER
header and designed routing list extension, the BIER nodes will
process the designed routing list in the BIER header and forward the
packet according to the list.
The current nodes receive a packet from the control plane or one
previous node. The current nodes will process the designed routing
list due to the indication in the BIER header. If there is no
indication of designed routing list in the BIER header, the current
nodes will forward the packet according to the BIER forwarding
defined in [I-D.ietf-bier-architecture].
If there is a designed routing list in the BIER header, the current
nodes will forward the packet due to the rules below.
Zhang & Wu Expires May 4, 2016 [Page 7]
Internet-Draft Designed Routing in BIER Forwarding November 2015
At first, if the node is one of the egress nodes due to the BIER
header, the nodes should decapsulate the packet and forward it to
outside.
Second, if the node detect that there is a designed routing list in
the BIER header, the node will process the designed routing list, and
forward the packet to the nodes in the list. The detail of
processing is described in the subsection.
At last, the node increases the current level in the designed routing
list, and forwards the packet to the next level nodes in the list.
6.1. Process the designed routing list
Step 1, the node gets the nodes' list in the designed routing list
belong to current level. For example, if the value of current level
field is set to 1, then the node will get the nodes that are
encapsulate in level 1.
Step 2, the node looks up the BIER forwarding table and gets the
table items which the next-hop are same to the nodes that get from
the designed routing list.
Step 3, the node copies the bitstring in the BIER header and updates
it by AND'ing with all the table items. After INVERSE the result, do
And'ing with the original bitstring. Then the result is reserved
egress nodes. It can be simplified to Rev-enodes.
Step 4, the node update the origin bitstring by AND'ing with one item
that are get from step2, and merge the result with the Rev-enodes,
increase the current level field by 1 and forwards the packet to the
next-hop of the item. If there are several items get from step2, the
node will do the processing with all the items.
Every node in the designed routing list repeats the step, the packet
will be forwarded by the nodes in the designed routing list. At last
the packet is forwarded to outside of the BIER domain.
As the example of section 4,
Suppose that the BitPositions for all nodes are:
A(1),B(2),C(3),D(4),E(5),F(6),G(7),H(8), K(9). And suppose that the
BSL is 9.
Zhang & Wu Expires May 4, 2016 [Page 8]
Internet-Draft Designed Routing in BIER Forwarding November 2015
---10---- B --10---- C --10---- D
| |
| 50
| |
A--20-----E --20---- F
| |
| 50
| |
---10---- G --10---- H --10--- K
Figure 7
The packet BIER header that is sent to D/F/K is encapsulated with
100101000. The path that we want the packet to travel is: E---F---C/
H---D/K. A is an ingress node, so the path list is escapsulated
with: level1: E level2: F level3: C/H level4: D/K
After OSPF/ISIS calculation, The BIER forwarding tables are:
Node A:
000001110 B
000110000 E
111000000 G
Node C:
111010011 B
000001000 D
000100000 F
Node D:
111110111 C
Node E:
111001111 A
000100000 F
Node F:
001010011 E
Zhang & Wu Expires May 4, 2016 [Page 9]
Internet-Draft Designed Routing in BIER Forwarding November 2015
000001100 C
110000000 H
Node H:
001011111 G
000100000 F
100000000 K
Node K:
011111111 H
The header of packet is: 100101000.
Now the process on node A is:
1, A looks at the path list, and finds that E is next node, A picks
out the routing item which next-hop is E from the forwarding table,
get the item"000110000"; Because the node in this level is only F, so
we only pick out one item of F.
2, Use the header of packet"100101000" AND the item of E"000110000";
the result is "000100000";
3, Now INVERSE the result"000100000", will get "111011111". Let we
use the header "100101000" AND the "111011111", we get the "Rev-
enodes""100001000";
4, A is ready to forward the packet to E, according to the rule
defined in BIER-arch, the header"100101000" AND the item which next-
hop is E"000110000", and OR the "Rev-enodes" "100001000", the result
is still "100101000", A sends the packet with the header"100101000"
to E.
The process on node E is:
5, When E receives the packet with header"100101000", E look at the
path list, fine that F is next node. E pick out the routing item
which next-hop is F from the forwarding table, get the
item"000100000". Because the node in this level is only F, so we
only pick out one item of F.
6, Use the header of packet"100101000" AND the item of F"000100000";
the result is "000100000";
Zhang & Wu Expires May 4, 2016 [Page 10]
Internet-Draft Designed Routing in BIER Forwarding November 2015
7, Now INVERSE the result"000100000", will get "111011111". Let we
use the header"100101000" AND the "111011111", we get the "Rev-
enodes""100001000";
8, E is ready to forward the packet to F, according to the rule
defined in BIER-arch, the header"100101000" AND the item which next-
hop is F"000100000", and OR the "Rev-enodes""100001000", the result
is still "100101000", E sends the packet with the header"100101000"
to F.
The process on node F is:
9, When F receives the packet with header"100101000", at first F find
that F itself is one of the egress nodes, after decapsulated and
forwarded the packet out of BIER domain, F clears own bit in packet
header, the header change to"100001000";
10, F looks at the path list, find that C and H are next nodes. F
picks out the routing item which next-hop is C from the forwarding
table, gets the item"000001100"; and F picks out the routing item
which next-hop is H from the forwarding table, gets the
item"110000000";
11, Use the header of packet"100001000" AND the item of C"000001100";
the result is "000001000". And we use the header"100001000" AND the
item of H"110000000"; the result is "100000000". Because there are
two results, so the mix result is "100001000".
12, Now INVERSE the result"100001000", will get "011110111". Let we
use the header"100001000" AND the "011110111", we get the "Rev-
enodes""000000000";
13, F is ready to forward the packet to C, according to the rule
defined in BIER-arch, the header "100001000" AND the item which next-
hop is C"000001100", and OR the "Rev-enodes""000000000", the result
is"000001000", F then sends the packet with the header"000001000" to
C.
14, similar to 13, F is ready to forward the packet to H, according
to the rule defined in BIER-arch, the header"100001000" AND the item
which next-hop is H"110000000", and OR the "Rev-enodes" "000000000",
the result is"100000000", F then send the packet with the header
"100000000" to H.
The process on node C is:
15, When the packet which header"000001000" reaches C, C will find
that D and K are next nodes. C picks out the routing item which
Zhang & Wu Expires May 4, 2016 [Page 11]
Internet-Draft Designed Routing in BIER Forwarding November 2015
next-hop is D from the forwarding table, gets the item"000001000".
And there is no routing item which next-hop is K in the forwarding
table, so we only get one item which next-hop is C.
16, Use the header of packet"000001000" AND the item of C"000001000";
the result is "000001000";
17, Now INVERSE the result"000001000", will get "111110111". Let we
use the header"000001000" AND the "111110111", we get the "Rev-
enodes""000000000";
18, C is ready to forwards the packet to D, according to the rule
defined in BIER-arch, the header"000001000" AND the item which next-
hop is C"000001000", and OR the "Rev-enodes""000000000", the result
is"000001000", C then send the packet with the header"000001000" to
D.
The process on node H is:
19, similar to the process in node C, node H will send the packet
with header"100000000" to K.
The process on node D and K are:
20, When the packet reaches D and K, the process is follow the rules
defined in BIER-arch, the packet is decapsulated and forwarded out of
BIER domain.
The brief process is:
Node A receives the packet from the control plane. The current level
field is 1. Node A gets node E from the designed routing list due to
the current level. Then node A lookups the BIER forwarding table and
gets the item which the next-hop is node E.
Because the shortest path from node A to node D and K is not go
through node E, so the node A will get the Rev-enodes that include
node D and K due to the steps in section 6.1. Node A forwards the
packet to node E, with the bitstring in the BIER header is set to D,
F and K, and the current level field is set to 2.
Node E receives the packet from node A, finds the items from the BIER
forwarding table which the next-hop is node F, do the same steps, set
the current level field to 3, and then forwards the packet to F.
Node F receives the packet from node E. At first node F decapsulates
the packet and forwards it outside of the BIER domain due to the
bitstring in the BIER header. Then node F finds the items from the
Zhang & Wu Expires May 4, 2016 [Page 12]
Internet-Draft Designed Routing in BIER Forwarding November 2015
BIER forwarding table which the next-hop is node C and H, does the
same steps in section 6.1, increase the current level value and
forward to node C and H.
Node C and H receive the packet from node F separately, repeat the
steps, increase the current level value to 4 and forwards it to node
D and K.
Node D and node K receive the packet from node F, repeat the steps,
decapsulate the packet and forward it out the BIER domain.
7. Security Considerations
For general BIER Security Considerations.
8. IANA Considerations
IANA is requested to allocate types in TLVs of BIER header.
9. Normative References
[I-D.ietf-bier-architecture]
Wijnands, I., Rosen, E., Dolganow, A., Przygienda, T., and
S. Aldrin, "Multicast using Bit Index Explicit
Replication", draft-ietf-bier-architecture-02 (work in
progress), July 2015.
[I-D.ietf-bier-mpls-encapsulation]
Wijnands, I., Rosen, E., Dolganow, A., Tantsura, J., and
S. Aldrin, "Encapsulation for Bit Index Explicit
Replication in MPLS Networks", draft-ietf-bier-mpls-
encapsulation-02 (work in progress), August 2015.
[I-D.ietf-bier-use-cases]
Kumar, N., Asati, R., Chen, M., Xu, X., Dolganow, A.,
Przygienda, T., arkadiy.gulko@thomsonreuters.com, a.,
Robinson, D., and V. Arya, "BIER Use Cases", draft-ietf-
bier-use-cases-01 (work in progress), August 2015.
Authors' Addresses
Zhang & Wu Expires May 4, 2016 [Page 13]
Internet-Draft Designed Routing in BIER Forwarding November 2015
Sandy Zhang
ZTE Corporation
No. 50 Software Ave, Yuhuatai Distinct
Nanjing 210000
China
Phone: +86-025-88014634
Email: zhang.zheng@zte.com.cn
Bo Wu
ZTE Corporation
No. 50 Software Ave, Yuhuatai Distinct
Nanjing 210000
China
Phone: +86-025-88016575
Email: wu.bo@zte.com.cn
Zhang & Wu Expires May 4, 2016 [Page 14]
