Internet DRAFT - draft-xu-rtgwg-twod-ip-routing
draft-xu-rtgwg-twod-ip-routing
Network Working Group M. Xu
Internet-Draft J. Wu
Intended status: Standards Track Tsinghua University
Expires: 25 September 2022 S. Yang
L. Cui
Shenzhen University
D. Wang
Hong Kong Polytechnic University
24 March 2022
Two Dimensional IP Routing Architecture
draft-xu-rtgwg-twod-ip-routing-01
Abstract
This document describes Two Dimensional IP (TwoD-IP) routing, a new
Internet routing architecture which makes forwarding decisions based
on both source address and destination address. This presents a
fundamental extension for traditional routing mechanism, which makes
forwarding decisions based on destination addresses to provides
reachability services. Such extension provides rooms to solve
fundamental problems of the past and foster great innovations in the
future.
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 https://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 25 September 2022.
Copyright Notice
Copyright (c) 2022 IETF Trust and the persons identified as the
document authors. All rights reserved.
Xu, et al. Expires 25 September 2022 [Page 1]
Internet-Draft TwoD-IP Routing Architecture March 2022
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://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 to this document. Code Components
extracted from this document must include Revised BSD License text as
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Benefits of Introducing TwoD-IP Routing . . . . . . . . . . . 3
2.1. Multi-homing . . . . . . . . . . . . . . . . . . . . . . 3
2.2. Load Balancing . . . . . . . . . . . . . . . . . . . . . 4
2.3. Policy Routing . . . . . . . . . . . . . . . . . . . . . 5
2.4. Others . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Framework . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4. Routing Protocol Design . . . . . . . . . . . . . . . . . . . 7
4.1. Protocol Overview . . . . . . . . . . . . . . . . . . . . 7
4.2. Router Actions . . . . . . . . . . . . . . . . . . . . . 8
4.3. TwoD-IP Routing Table Construction . . . . . . . . . . . 9
5. Forwarding Table Design . . . . . . . . . . . . . . . . . . . 10
6. Deployment . . . . . . . . . . . . . . . . . . . . . . . . . 11
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 11
8. Security Considerations . . . . . . . . . . . . . . . . . . . 11
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 11
10.1. Normative References . . . . . . . . . . . . . . . . . . 11
10.2. Informative References . . . . . . . . . . . . . . . . . 12
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12
1. Introduction
Since IP routing took place, the current Internet has been making
forwarding decisions based on destination addresses. The
destination-based routing system provides limited semantics with only
a single path towards each destination. Many services, such as
multi-homing, multi-path and traffic engineering, face difficulties
within the current Internet routing system. Due to the important
semantics of source address, recent years see increasing works on
adding source addresses into routing controls.
Xu, et al. Expires 25 September 2022 [Page 2]
Internet-Draft TwoD-IP Routing Architecture March 2022
IP source routing [3] carries the routes in packet header. However,
IP source routing is disabled in most networks due to security
reasons. MPLS [4] uses label switching to manage traffic per-flow.
However, MPLS raises scalability issues when the number of label
switching paths (LSPs) increases [5]. What's more, many ISPs prefer
pure-IP networks.
In this draft, we describe Two Dimensional IP (TwoD-IP) routing,
which makes forwarding decisions based on both source and destination
addresses. TwoD-IP routing presents a fundamental extension of the
semantics from the current Internet. The network will become more
flexible, manageable, reliable, etc. Such extension provides rooms
to solve problems of the past and foster innovations in the future.
This document also presents the deployment issues and objectives of
the TwoD-IP routing.
2. Benefits of Introducing TwoD-IP Routing
In this section, we list the use cases that can benefit from TwoD-IP
routing.
2.1. Multi-homing
Multi-homing is prevalent among ISPs for better traffic distribution
and reliability. Traditionally, Provider Independent (PI) address is
used. Because PI address can not be aggregated by higher level ISPs,
it will cause explosion of routing table. To solve the problem,
Provider Aggregatable (PA) address is proposed. However, PA address
complicates network configurations for ISP operators. Besides, due
to destination-based routing in traditional networks, PA address has
difficulties when facing failures, i.e., the network has to re-
compute a new path when failures happen.
Xu, et al. Expires 25 September 2022 [Page 3]
Internet-Draft TwoD-IP Routing Architecture March 2022
+--------------------+
| |
| Internet |
| |
+--+---------------+-+
| |
| l3 | l4
| |
+------+----+ +--+--------+
| ISP1 | | ISP2 |
| Prefix P1 | | Prefix P2 |
+--------+--+ +-+---------+
| |
| l1 | l2
+--+------------+--+
| |
| Multi-homed Site | +---------+
| +--------+ Host |
+------------------+ +---------+
ISP1 address: A
ISP2 address: B
Figure 1: TwoD-IP routing for multi-homing
For example, in Figure 1, assume a multi-homed site is connected to
two ISPs: ISP1 and ISP2. ISP1 has a prefix P1, and ISP2 has a prefix
P2. A host connect to the multi-homed site has two addresses,
address A that can be aggregated into P1, and address B that can be
aggregated into P2. With TwoD-IP routing, the multi-homed site can
deliver the traffic from A towards the Internet to ISP1, and deliver
the traffic from B towards the Internet to ISP2. If the host is
using address A, and the link l1 or l3 fails. Then the host can
immediately detect the failure, then switch to address B, and
continue to communicate with the Internet via ISP2. With TwoD-IP,
the host does not have to wait for routing convergence in the multi-
homed site when failures happen.
2.2. Load Balancing
Compared to destination-based routing, TwoD-IP routing can manipulate
traffic in a finer-grained granularity. Such that TwoD-IP can
achieve better traffic distribution. For example, in Figure 2,
assume that there are 5 hosts that are communicating with the same
server at 10Mbps. Our goal is to minimize the maximum link
utilization over the network. Within destination-based routing,
traffic towards the same destination has to travel along the same
path in the network. Thus the best traffic distribution is to let
Xu, et al. Expires 25 September 2022 [Page 4]
Internet-Draft TwoD-IP Routing Architecture March 2022
all traffic take the north route via router b, and the Min-max link
utilization is 83.3%.
+-----+
|Host1+---+
+-----+ |
+-----+ | 60Mbps +-----+ 60Mbps
|Host2+---+ +--------+ b +---------+
+-----+ | | +-----+ |
+-----+ | +--+--+ +--+--+ +------+
|Host3+---+---+ a | | c +--------+Server|
+-----+ | +--+--+ +--+--+ +------+
+-----+ | | +-----+ |
|Host4+---+ +________+ d |_________+
+-----+ | 40Mbps +-----+ 40Mbps
+-----+ |
|Host5+---+
+-----+
Figure 2: TwoD-IP routing for load balancing
With TwoD-IP routing, we can let the traffic of three hosts (e.g.,
Host1, Host2 and Host3) take the north route via b, and let the
traffic of the other two hsots (e.g., Host4 and Host5) take the south
route via d. Thus the Min-max link utilization is only 50.0%.
2.3. Policy Routing
Assume in an ISP network, ISP operator wants that the traffic from
source address A towards destination address B passes by router C.
With TwoD-IP routing, routers make forwarding decisions based on both
destination and source addresses, thus can easily identify the
traffic from A towards B, and divert it to the next hop towards C.
2.4. Others
Besides the above-mentioned use cases, TwoD-IP routing is beneficial
in many other use-cases. We list the other use-cases briefly.
* Reliability: TwoD-IP provides multiple paths towards destination,
rather than the shortest path only. When one path breaks down,
routers can immediately switch to another path.
Xu, et al. Expires 25 September 2022 [Page 5]
Internet-Draft TwoD-IP Routing Architecture March 2022
* Multi-path: TwoD-IP can forward packets towards the same
destination, and from different sources to different next hops.
If a host has multiple source addresses, the host will have
multiple paths towards the same destination.
* Security: Traditional network pushes the security devices to the
border routers, the intermediate network just delivers the
packets. With TwoD-IP, intermediate routers also have source
checking functionality. Thus, the whole network rather than the
border network, can defense attacks.
3. Framework
In traditional routing, the control plane is concerned with the
network status, e.g., network topology. Within TwoD-IP routing, the
control plane is concerned with both network status and user demands.
TwoD-IP routing not only provides basic connectivity service, but
also satisfies kinds of user demands, e.g., policy routing, multi-
path and traffic engineering. TwoD-IP routing protocol has two
components:
* Destination-based routing protocol: To be compatible with
traditional routing (especially when most networks only support
destination-based routing), TwoD-IP routing protocol should
support destination-based routing. Such that ISPs can provide the
same connectivity service, while upgrading routers with TwoD-IP
functionality. To provide better connectivity services,
destination-based routing protocol should respond instantly to the
changes of network topology.
* Source-related routing protocol: Combined with source addresses,
TwoD-IP routing can make better forwarding decisions for users.
Source-related routing protocols focus on providing services that
are related with source addresses. They may need to collect
demands from users, and compute the routing table to satisfy these
demands. Depending on the specific user demands, some source-
related routing protocols need real-time updates, while others do
not. The newly designed source-related routing protocols should
be:
- Consistent, they should be consistent with other routing
protocols, including the destination-based routing protocol and
other new source-related routing protocols;
- Efficient, they should not bring lots of additional overheads
to the network.
Xu, et al. Expires 25 September 2022 [Page 6]
Internet-Draft TwoD-IP Routing Architecture March 2022
* There are multiple ways to implement source-related routing
protocol, such as, 1) updating OSPF [8] or IS-IS [7] protocols to
support source-related protocols; 2) using segment routing [9] or
software defined network controller to divert traffic according to
user demands.
4. Routing Protocol Design
4.1. Protocol Overview
In this section, to illustrate TwoD-IP routing protocol, we design a
simple policy routing protocol. The routing protocol provides a
flexible tool for ISPs to divert traffic (that is from some customer
networks towards the foreign Internet) to another path.
+---------+
|0.0.0.* | +-----------------------+ +----------+
| +-----+-B0 I3 ------ E0-+-----+ |
+---------+ | ) ( | | 1.0.0.* |
Domain number=0 | ) ( | | |
The first customer | I0 | | 1.0.1.* |
+---------+ | ) ( | | |
|0.0.1.* | | ) ( | | 1.0.2.* |
| +-----+-B1 I1---I2---E1-+-----+ |
+---------+ +-----------------------+ +----------+
Domain number=1 ISP network Foreign Internet
The second customer
Figure 3: A simple policy routing protocol
For example, in Figure 3, the ISP has two customer networks, the
first customer network has domain number of 0 and one prefix of
0.0.0.*, the second customer network has domain number of 1 and one
prefix of 0.0.1.*. The first customer network is conneted to provider
edge router (PE router) B0 and the second customer network is
connected to PE router B1. The ISP is connected to the foreign
Internet through two edge routers, E0 and E1, besides, it has four
intermediate routers (P router), I0, I1, I2 and I3. The shortest
paths from the customer networks to the foreign Internet are
B0-I0-I3-E0 and B1-I0-I3-E0. However, due to congestion on E0, the
ISP operator wants to divert the traffic of the second customer
network (behind B1) to the path through E1, i.e., B1-I0-I1-I2-E1.
We design the protocol based on the extension of OSPF [2], which can
disseminate the information within the network. To illustrate the
protocol, we first clarify the following aspects.
Xu, et al. Expires 25 September 2022 [Page 7]
Internet-Draft TwoD-IP Routing Architecture March 2022
* Through e-BGP, edge routers know the prefixes of foreign Internet,
e.g., both E0 and E1 know that there are three foreign Internet
prefixes, 1.0.0.*, 1.0.1.*, 1.0.2.*;
* Through OSPF, PE routers know the prefixes of the customer
networks behind them, e.g., B0 knows that prefix 0.0.0.* belong to
the first customer network in Figure 3. Besides, PE routers know
the customer domain number of the customer networks behind them,
e.g, B0 knows that the customer domain number of the first
customer network is 0. Through manual configuration or automatic
selection (e.g., selecting the router that has lower utilization),
edge routers know the preferences of customer networks on edge
routers, e.g., B1 knows that the second customer network in
Figure 3 prefers to pass by E1.
With these preconditions, each edge router can announce the foreign
Internet prefixes combined with its own router identification to the
network, each PE router can announce the customer prefixes combined
with the corresponding customer domain number, PE routers are also
responsible for announcing the preference of customer networks on
edge routers. When receiving all necessary information, both PE and
P routers will construct the routing table, which can be used to
generate the forwarding table.
4.2. Router Actions
We first define three types of messages.
Announce(Prefixes, Router_ID): Edge routers send this message, to
announce the binding relations between foreign IP perfixes and the
edge router identification (can be represented by the IP address
of the edge router). This message indicates that traffic can
reach the foreign Internet through the edge router.
Bind(Prefixes, Domain_Number): PE routers send this message, to
announce the binding relations between customer network IP
prefixes and customer domain number. This message indicates that
the customer network IP prefixes belong to the cusomter network
that owns the Domain_Number.
Pref(Domain_Number, Router_ID): PE routers send this message, to
announces the preference of a customer network on an edge router.
This message indicates that the customer network that owns the
Domain_Number prefers to pass by the edge router that owns the
Router_ID.
Then the actions on different types of routers are as follows.
Xu, et al. Expires 25 September 2022 [Page 8]
Internet-Draft TwoD-IP Routing Architecture March 2022
Edge Routers: Edge routers have to send Announce(Prefixes,
Router_ID) to announce the foreign Internet prefixes to the
network. For example, in Figure 3, E0 will send Announce(1.0.0.*,
E0), Announce(1.0.1.*, EO) and Announce(1.0.2.*, EO). E1 will
send Announce(1.0.0.*, E1), Announce(1.0.1.*, E1) and
Announce(1.0.2.*, E1).
PE Routers:
1. PE routers have to send Bind(Prefixes, Domain_Number) to
announce the customer network prefixes to the network. For
example, B0 will send Bind(0.0.0.*, 0), B1 will send
Bind(0.0.1.*, 1).
2. PE routers have to send Pref(Domain_Number, Router_ID) to
announce the preference of the cusomter network on an edge
routers. For example, B1 will send Pref(1, E1).
3. After receiving Announce(Prefixes, Router_ID) from edge
routers, PE routers should construct the routing table.
Intermediate Routers: After receiving Announce(Prefixes, Router_ID)
from edge routers, Bind(Prefixes, Domain_Number) and
Pref(Domain_Number, Router_ID) from PE routers, P routers should
construct the routing table.
4.3. TwoD-IP Routing Table Construction
Receiving the necessary information (including customer network
prefixes, foreign Internet prefixes and preferences of customer
networks), both PE and P routers should construct the routing table.
Edge routers do not need to construct the routing table, unless they
also belong to PE/P routers.
The routing table consists of two parts, the first part (traditional
routing table) is constructed based on OSPF, the second part (TwoD-IP
routing table) is construted based on our TwoD-IP policy routing
protocol. When forwarding a packet to the destination, routers first
lookup the TwoD-IP routing table, if there does not exist a matched
entry, routers will lookup the traditional routing table. We focus
on the construction of TwoD-IP routing table in this document. For
simplicity, we assume that there are only threee fields in each entry
of TwoD-IP routing table, i.e., (Destination, Source, Next hop).
Both the destination and source fields represent an IP prefix, the
next hop field denotes the outgoing router interface to use (see
Section 11 of [1] for more details).
The routing table construction process is as follows.
Xu, et al. Expires 25 September 2022 [Page 9]
Internet-Draft TwoD-IP Routing Architecture March 2022
1. For each received Pref(Domain_Number, Router_ID), lookup the
traditional table, and obtain the next hop towards the edge
router that owns Router_ID. We use Next_Hop to denote the
obtained next hop.
2. For each foreign Internet prefix (Foreign_Prefix), lookup the
traditional table, and obtain the next hop towards the
Foreign_Prefix. We use Next_Hop' to denote the obtained next
hop.
3. If Next_Hop!=Next_Hop', for each customer network prefix
(Customer_Prefix) that belongs to the customer network that own
Domain_Number, we add a new entry (Foreign_Prefix,
Customer_Prefix, Next_Hop) to the TwoD-IP routing table.
For example, we continue the example in Figure 3, the TwoD-IP routing
table on the P router I0 is shown in Figure 4.
Destination Source Next hop
_______________________________________________________
1.0.0.* 0.0.1.* I1
1.0.1.* 0.0.1.* I1
1.0.2.* 0.0.1.* I1
Figure 4: TwoD-IP routing table on the P router I0
5. Forwarding Table Design
The forwarding table stores a set of 3-tuple rules, {pd, ps, nh},
where pd is a destination prefix, ps is a source prefix, and nh
indicates the next hop. When a packet arrives, if its destination
address matches pd according to LMF (longest match first) rule among
all rules, and its source address matches ps according to LMF rule
among all rules that are associated with pd. Then the router will
forward the packet to the next hop nh.
The forwarding table design could be based on extension to TCAM, or
algorithmic lookup in SRAM. The newly designed forwarding table
should satisfy the following requirements.
* Storage requirement: The new forwarding table should not cause
forwarding table explosion problem. Current storage technology
should be able to accomodate the table.
Xu, et al. Expires 25 September 2022 [Page 10]
Internet-Draft TwoD-IP Routing Architecture March 2022
* Speed requirement: The new forwarding table should match line-
speeds.
6. Deployment
TwoD-IP should support incremental deployment, and during deployment,
the following requirements should be satisfied.
Backward compatibility: During deployment, reachability should be
guaranteed, and loops should be avoided.
Incentive: After deploying partial routers, ISPs should be able to
see visible gains, e.g., their policies are implemented, traffic
distribution is improved or security level is enhanced.
Effectivity: The deployment should maximize the benefits for ISPs,
e.g., the deployment sequence should be carefully scheduled, such
that ISPs can obtain maximum benefits in each step.
7. Implementation Status
We have developed a prototype of the TwoD-IP policy routing protocol
(see Section 4) based on Quagga, and set up tests with a small scale
testbed.
8. Security Considerations
TwoD-IP routing will enhance the security level of the networks,
because routers will check source addresses, which is an important
identity of the senders. Distributed attack defenses will be an
important topic of TwoD-IP routing, because source checking
functionality is deployed deeper in the network.
However, TwoD-IP routing protocols must be carefully designed, to
avoid to be used by hackers.
9. IANA Considerations
Some newly designed TwoD-IP routing protocols may need new protocol
numbers assigned by IANA.
10. References
10.1. Normative References
[1] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
DOI 10.17487/RFC2328, April 1998,
<https://www.rfc-editor.org/info/rfc2328>.
Xu, et al. Expires 25 September 2022 [Page 11]
Internet-Draft TwoD-IP Routing Architecture March 2022
[2] Zinin, A., Roy, A., Nguyen, L., Friedman, B., and D.
Yeung, "OSPF Link-Local Signaling", RFC 5613,
DOI 10.17487/RFC5613, August 2009,
<https://www.rfc-editor.org/info/rfc5613>.
[3] Estrin, D., Li, T., Rekhter, Y., Varadhan, K., and D.
Zappala, "Source Demand Routing: Packet Format and
Forwarding Specification (Version 1)", RFC 1940,
DOI 10.17487/RFC1940, May 1996,
<https://www.rfc-editor.org/info/rfc1940>.
[4] Rosen, E., Viswanathan, A., and R. Callon, "Multiprotocol
Label Switching Architecture", RFC 3031,
DOI 10.17487/RFC3031, January 2001,
<https://www.rfc-editor.org/info/rfc3031>.
[5] Yasukawa, S., Farrel, A., and O. Komolafe, "An Analysis of
Scaling Issues in MPLS-TE Core Networks", RFC 5439,
DOI 10.17487/RFC5439, February 2009,
<https://www.rfc-editor.org/info/rfc5439>.
10.2. Informative References
[6] Breitbart, Y., Chan, Chee-Yong., Garofalakis, M., Rastogi,
R., and A. Silberschatz, "Efficiently monitoring bandwidth
and latency in IP networks", INFOCOM 2001, April 2001.
[7] Baker, F. and D. Lamparter, "IPv6 Source/Destination
Routing using IS-IS", Work in Progress, Internet-Draft,
draft-baker-ipv6-isis-dst-src-routing-07, 18 July 2017,
<https://www.ietf.org/archive/id/draft-baker-ipv6-isis-
dst-src-routing-07.txt>.
[8] Baker, F., "IPv6 Source/Destination Routing using OSPFv3",
Work in Progress, Internet-Draft, draft-baker-ipv6-ospf-
dst-src-routing-03, 28 August 2013,
<https://www.ietf.org/archive/id/draft-baker-ipv6-ospf-
dst-src-routing-03.txt>.
[9] Xu, M., Wang, B., Wang, T., Yang, S., and J. Wu, "Segment
Routing in Two Dimensional IP Routing", Work in Progress,
Internet-Draft, draft-xu-spring-segment-twod-ip-routing-
01, 24 February 2022, <https://www.ietf.org/archive/id/
draft-xu-spring-segment-twod-ip-routing-01.txt>.
Authors' Addresses
Xu, et al. Expires 25 September 2022 [Page 12]
Internet-Draft TwoD-IP Routing Architecture March 2022
Mingwei Xu
Tsinghua University
Department of Computer Science, Tsinghua University
Beijing
100084
P.R. China
Phone: +86-10-6278-5822
Email: xmw@cernet.edu.cn
Jianping Wu
Tsinghua University
Department of Computer Science, Tsinghua University
Beijing
100084
P.R. China
Phone: +86-10-6278-5983
Email: jianping@cernet.edu.cn
Shu Yang
Shenzhen University
South Campus, Shenzhen University
Shenzhen
518060
P.R. China
Phone: +86-755-2653-4078
Email: yang.shu@szu.edu.cn
Laizhong Cui
Shenzhen University
South Campus, Shenzhen University
Shenzhen
518060
P.R. China
Phone: +86-755-8695-6280
Email: cuilz@szu.edu.cn
Dan Wang
Hong Kong Polytechnic University
Department of Computing, Hong Kong Polytechnic University
Hong Kong
P.R. China
Phone: +852-2766-7267
Email: csdwang@comp.polyu.edu.hk
Xu, et al. Expires 25 September 2022 [Page 13]
