Flexible Routing with Policy Exchange
Bin Gui, Fangping Lan, Anduo Wang
Temple University
Philadelphia, USA. . . how to make the fitting adjustment between
individual independence and social control . . . That
principle is, that the sole end . . . in interfere with theliberty of [any of their member], is self protection. Thatthe only purpose is . . . to prevent harms to others.

ABSTRACTBGP and its alternatives alike, struggle with distributed policy making in the absence of a central authority: BGP prioritizes independence of the participating networks (e.g., ASes),
imposes zero coordination, but has to tolerate inflexible policies each network can express. On the other hand, BGP alternatives (source routing, for example), through coordination,
trade independence for flexibility, but only achieve flexibility
partially. This paper asks, to achieve flexible routing, what is
the fitting adjustment between network independence andcoordination? To answer this question, we propose a simple
principle that the sole end to interfere with the flexibility ofa participating network is to prevent harms — decreasing
the level of flexibility — to others. As an instantiation of thisprinciple, we introduce the concept of policy exchange thatdynamically adjusts independently set policies on the fly, anddevelop a preliminary implementation with conditional table, a strong knowledge representation system that allows us
to distribute and manipulate policies with the usual SQL-like
operators. Our preliminary experiments on realistic network
topology and synthetic policies are encouraging.

CCS CONCEPTS• Networks → Routing protocols; Network management; •Computing methodologies → Reasoning about belief andknowledge.

KEYWORDS
Policy exchange, interdomain routing, conditional tables,
knowledge representation
ACM Reference Format:
Bin Gui, Fangping Lan, Anduo Wang. 2021. Flexible Routing with
Policy Exchange. In 5th Asia-Pacific Workshop on Networking (APNet 2021) (APNet 2021), June 24–25, 2021, Shenzhen, China, China.
ACM, New York, NY, USA, 7 pages. https://doi.org/10.1145/3469393.
3469395
Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are notmade or distributed for profit or commercial advantage and that copies bear
this notice and the full citation on the first page. Copyrights for componentsof this work owned by others than ACM must be honored. Abstracting withcredit is permitted. To copy otherwise, or republish, to post on servers or toredistribute to lists, requires prior specific permission and/or a fee. Request
permissions from permissions@acm.org.
APNet 2021, June 24–25, 2021, Shenzhen, China, China© 2021 Association for Computing Machinery.
ACM ISBN 978-1-4503-8587-9/21/06. . . $15.00
https://doi.org/10.1145/3469393.3469395

John Stuart Mill, On Liberty

1

INTRODUCTION

The Internet consists of independently operated networks(i.e. autonomous systems, or ASes) that use dissimilar policies
to collectively drive global routing. It is probably the mostimportant instance of — in the absence of a central authority— distributed policy making [1, 2, 7, 11, 31, 33, 34]. And Border
Gateway Protocol (BGP) [32] is the one and only routing
protocol that supports such policies.
One reason that contributes to BGP’s uniqueflexibility
role is the extreme poBGP alternatives
sition taken by BGP(source routing,multipath,that aligns itself withoverlay …)
the network owners:
BGP
Route preference cancoordination
be arbitrary and set
solely based on local metrics; only the
independence
best route used for
Figure 1: To achieve flexibilpacket forwarding isity, what is the fitting adjustre-districted to selected
ment between network indeneighbors from which
pendence and coordination?
packets are allowed;
only the route itself is
exposed while the policies governing the routing process
are sensitive information, thus are hidden from the externalInternet. Together, these designs make the operation of each
AS independent from the rest of the Internet, and the AS
policies are affected only by direct neighbors; But the same
design also makes distributed policies inflexible: the networkedge and the transit ASes alike have little control over traffic path, their influences are often limited to the first hop.
As summarized in Figure 1, BGP prioritizes individual independence, tolerates routing inflexibility, and refrains fromremote coordination.
In contrast, many attempts to improve and/or replace BGP
strive for more flexible policies, and do not shy away fromcoordination. Source routing [5, 15, 37, 38] allows the source
AS to control the entire path, multi-path routing [13, 20, 36]

APNet 2021, June 24–25, 2021, Shenzhen, China, China

improves transit AS’s visibility to available paths via multiple routes computation. Besides, most of these schemes
improve flexibility only at selected participants with best effort: Source routing enhances the sources with more choicesat the cost of the transits; multipath routing improves path diversity at the upstream nodes at the cost of the downstream.
In sum they only achieve flexibility partially.
In light of the fundamental tradeoff in the foregoing discussion, this paper asks, to achieve flexible routing, what is thefitting adjustment between network independence and global
coordination? To answer this question, we argue for a simple
principle that the sole end to interfering with the flexibility of a
network is to prevent harms — decreasing the level of flexibility— to others.
The principle implies that a flexible routing system should
support all legitimate policies — those can be satisfied alongsome existing paths while not hindering others. But existingrouting schemes, to our best knowledge, fail to admit all
legitimate policies.We study and map the failure scenarios
into two categories: Depending on the type of (unwanted)
policy interactions that leads to the failure, the first category involves an overly strong policy that perfectly matches
a node’s local concern but unnecessarily excludes policies
available to other nodes along the same path affecting overlapping traffic. In the second category, seemingly unrelated
policies affecting disjoint traffic, while legitimate on theirown, can mutually exclude each other if they cross a common
intermediate node. In both cases, the solution is to discover
the “right” policy that firmly expresses local interests, butalso adapts (generous) to others’ needs — including thoseover overlapping traffic, and those referencing a shared critical node — as much as possible. Our goal is to make suchintelligent policy discovery happen by exposing minimal
policy information.
Specifically, we introduce policy exchange in which independently set policies are iteratively exchanged between
direct neighbors, and adjusted as needed, in a hop by hopmanner like classic distance vector algorithm: Each participating network, upon receiving a policy fragment announcement from a direct neighbor — the announcement represents
that neighbor’s request to protect its internal concern that
potentially depends on external decisions, decides whether
to honor the request in the fragment: if the current node determines to support the neighbor’s concern, but figures thatit alone cannot guarantee the fragment within local means(e.g., tweaking local preference or route exporting policies),
the current node will then re-distribute the fragment — withtransformation to reflect its role as well as concealing theidentify of the original sender. The hope is that, by distributing only necessary policy fragments, policy exchange willretain the network independence we hold dear, as well asgive sufficient visibility into the rest of the Internet to locate
the right policy.

Bin Gui, Fangping Lan, Anduo Wang

To show that policy exchange is technically feasible, we
present a preliminary implementation with conditional tables [3, 4, 19], a knowledge representation system originatedin the database community. Conditional table enhances traditional tables with variables and tuple conditions, making
it a powerful knowledge representation for policies, allowing policies to be passed around like regular factual data.
More importantly, conditional tables allow the usual SQLlike data query and manipulation (select, join etc.), making
it a convenient vehicle for rapid prototyping of policy exchange mechanisms. We also note that policy exchange will
not magically remove all difficulties with distributed policy
making: Policy exchange will not move policy enforcement
to the most fitting location hence cannot be used to suppress
the impact of finer policies; and it does not detect or resolve
conflicts among simultaneously unsatisfiable policies. Nevertheless, our initial implementation is encouraging, and wehope that policy exchange, with some luck, may infect thedesign of a more flexible future Internet.

2

A SIMPLE PRINCIPLE (EXPLAINED) BY
FAILURES

Our main thesis is that a policy should be admitted as longas it does not harm others, that is a path p that satisfies thepolicy exists and that the selection of p does not eliminate
other policies. We say that a policy is legitimate if it is admittable. To guide our design towards a flexible routing system(detailed in § 3) that permits all legitimate policies, we analyze the scenarios when an inflexible routing system fails.
We map the failures into two categories depending on thetype of interaction that leads to the failure.
Policies affecting shared traffic along a single path.

s

policy (p3):for traffic to d1,
prefer 2 over 1

3

policy (p5):policy (p6, p7):
on behalf of s1,
on behalf of s2,s3,
secure traffic to d fast delivery to d
s1
s2
s3
5

1

d2

d1

p3?
0
d1
(1.2.3.4/24)

policy (p0):split traffic to d1/d2
between (1,0) and
(2,0)

d2
(5.6.7.8/24)

6

7

2
3

4

1

2

policy (p1):policy (p2):dsecurefast delivery
delivery for d (1.2.3.4/16) for d

Figure 2: Inflexibility scenarios mapped into two categories:(left) overly strong policy (p0 ) unawares of others eliminate
otherwise legitimate policies (p3 ) along the same path overshared traffic, (right) multiple policies that are seemingly independent can be mutually exclusive if they are realized onpaths that cross a common “critical” node.

Flexible Routing with Policy Exchange

The purpose of a policy is to codify a node’s (whether at the
granularity of an AS or a router) own traffic concerns (service
requirement or resource restriction). Yet an overly strong
policy statement, though perfectly captures the local interest,
may rob the choices available to other nodes along the same
path. When that is the only path that simultaneously satisfies
all the nodes along it, an overly strong policy placed by one
node effectively makes it impossible to admit a legitimate
policy of another node. This reduces the “overall” level offlexibility of the entire routing system.
For example, Figure 2 (left) depicts four ASes (nodes 0,1,2,3)
that compute paths to carry traffic between a (source) hosts and two (destination) prefixes d1 ,d2 . AS3’s policy p3 (onbehalf of s) desires traffic destined to d1 to go through themore preferred provider AS2. p3 is satisfiable: there exists apath [320] that not only complies with this restriction, but isalso compatible with AS0 whose policy p0 balances traffic to
d1 ,d2 . Whether p3 can actually be enforced or not, however,depends on how p0 is implemented — to split incoming traffic
AS0 can either instruct d1 traffic to use link (0,2) (d2 trafficon (0,1)), or instruct d1 to use (0,1) (d2 on (0,2)). Amongthe two options, only the former will expose path [20] toAS3, which in turn selects [320] and implements p0 . Lacking
visibility into of the upstream policy p3 , AS0 may blindly pickthe “wrong” implementation, announcing d1 to AS1 (d2 toAS2), and excluding the otherwise p3 -compliant path [320].
BGP is known to suffer from such inflexibility, and source
routing only address this problem partially: while source
routing allows A0 to expose p0 to the source — AS3 — whereroute selection is made, it does not prevent p3 from making
the overly strong policy that uses (0,2) for d1 (d2 traffic on(0,1)). That is, source routing allows route decision at thesource, but does not facilitate the downstream ASes to arriveat the right policy that increases choices at the source. To
accommodate every legitimate policy, the routing system needs
to facilitate individual AS to arrive at “informed” policies that
not only express its own concern, but are also aware of others— permitting as wide a latitude as possible in the constructionand enforcement of policies at other ASes.
Policies affecting disjoint traffic crossing a common
node.
Policies for disjoint traffic along separate paths can still
inadvertently interfere with each other. When the policy
compliant paths cross a common node, policy made at that
node to accommodate one flow of traffic may lead to therejection of another flow. Hence, the nodes at the potential“joint” must carefully craft their policies to simultaneously
admit all the flows (and the policies that defined them).
Consider the three source nodes (s1,s2,s3) and a destination prefix (d) in Figure 2 (right): Policy p5 demands secure
traffic delivery via some downstream AS1 (a firewall is probably deployed at AS1), p6 ,p7 require faster delivery via AS2. The
network can simultaneously accommodate all these policies
with the routes highlighted — the dashed and solid arrows

APNet 2021, June 24–25, 2021, Shenzhen, China, China

depict routes selected for traffic from s1 and s2/s3, respectively. This route selection, however, requires AS3 to make aproper decision p3 , taking into account the traffic requests
from all the hosts (s1,s2,s3), that is, honoring p5 but discarding p6 and p7. AS3 can arrive at this intelligent decision p3
only if AS3 has the knowledge that p5 can be implemented
only if it is accepted at AS3 — perhaps by charging AS5 withan extra fee, and that p6 ,p7 can still be satisfied even if they
are rejected at AS3.
BGP was not designed for joint policy routing as discussed
above; Source routing only improves the level of flexibility at
the sources, and multi-path routing allows multiple policies
at a single AS (e.g.,AS3), selecting different routes for each
upstream neighbor (e.g.,AS5, AS6), but neither addresses policy making at the potential joints because policy routes arestill computed in isolation. To accommodate multiple legitimate policies that are related because they rely on paths thatcross a common node, the routing system should facilitate that
common node to arrive at an “intelligent” decision that jointly
allocates routing resource — accommodating as many legitimate policies as possible.

3

A CASE OF POLICY EXCHANGE

This section develops policy exchange which instantiates the
do-no-harm principle in § 1, and addresses the failures analyzed in § 2. In policy exchange, policies are no longer fixed
term embedded in the route computation process, rather,
they become dynamic entities that can be adjusted to finetune their impacts on others. To capture the “policy impacts”,
we introduce the notion of policy fragment, a portion of an
AS policy that cannot be guaranteed within the local AS. A
policy fragment codifies what makes an AS vulnerable to thedecision by others, it is thus propagated hop by hop until it
is either (accepted and) incorporated into some remote AS’s
policy decision, or is explicitly rejected. The hope is that,by providing an exchange platform that gives individual AS
better visibility into how their local decisions affect others,
they will make better informed policies that raise flexibility
for everyone.
Algorithm 1 Policy Exchange at i
1: if ei (pi ) == f alse then // pi can be enforced within i
2:for each neighbor k do
3:
pik ← fk (pi ); // policy fragment relevant to k
4:

send pik to k;

5: loop (wait until i receive pki from some neighbor k)
6:
7:
8:
9:
10:

for each pki do
pi ← mi (pi , pki ); // merges pki with local policy
if ei (pi ) == f alse thenjpi ← fk (pi ) for every neighbor j;jsend pi to j;

APNet 2021, June 24–25, 2021, Shenzhen, China, China

Bin Gui, Fangping Lan, Anduo Wang

steppolicy exchange

p1

p2

p3

p4

p5

p6

p7

0
1
2
3
4
5

5→3: secure6(7)→3: fast; 6(7)→4: fast
3→5: secure(2); 3→6: fast(1); 3→7: fast(1)6→3: ¬fast(1); 6→4: ¬fast(1)7→3: ¬fast(1); 7→4: ¬fast(1)securesecuresecuresecuresecuresecure

fast
fast
fast
fast
fast
fast

⊤
securesecure(2), fast(1)secure(2), fast(1)secure(2), fast(1)secure(2)

⊤
⊤
fast
fast
fast
fast

securesecuresecuresecure(2)secure(2)secure(2)

fast
fast
fast
fast@4, ¬fast(1)@3
fast
fast

fast
fast
fast
fast@4, ¬fast(1)@3
fast@4, ¬fast(1)@3
fast

Table 1: One possible trace of policy exchange for the network in Figure 2 (right).

3.1

A Policy Exchange Protocol

Like routing information exchange, policy exchange is implemented at each policy-based routing entity. Each node
receives policy fragments from one or more of its directly
attached neighbors, performs a calculation, and then distributes the results of the calculation back to its neighbors:
the policy fragment specifies a service request (or a resource
restriction) placed on the receiving node by the sending
neighbor; the calculation estimates the impact of the request(resource), the results of which represent what cannot berealized within the receiving node — requiring support (compliance) from other neighbors, and hence must be further
distributed.
Specifically, as depicted in Algorithm 1: In line 1-4, node i
initializes its policy fragments — local request (or restriction)— that need to be exposed for realization; The fragment pik is
calculated by fk specific to each neighbor k, meaning that the
impact of the same local concern needs to be instantiated in
the context of each neighbor. In line 5-10, node i iteratively
exchanges policy fragments with all the neighbors: eachfragment received is first merged with the local policy via
mi , a merging function that adjusts i’s policy as follows:
simply combine pki and pi if the two are compatible witheach other; override pi with pki if conflict arises and i decides
to yield to neighbor k. Note that our protocol only develops a
policy exchange platform, where the specific implementationof e, f , m (and their semantics) is unspecified and left to theparticipating ASes. We will show possible instantiations ofthese functions by examples in § 3.2.
We illustrate the operation of policy exchange by revisiting the example in Figure 2 (right)1 . One specific execution trace, among many others due to the distributed andasynchronous nature of the policy exchange algorithm 1, issummarized in Table 1: At step 0, all ASes start with theirinitial policies, furthermore, AS5 sends its policy request fora secure route to d (5→3: secure), since AS5 depends on AS3
to get to d. This causes AS3 to change its policy from unconditional traffic delivery (⊤) to secure delivery (secure);
Likewise, at step 1, AS6 (AS7) sends a fast route request to its
two downstream neighbors AS3,AS4: while this causes AS4 to
adopt fast traffic delivery, the resulting policy of AS3 is moreinteresting, to merge the conflicting requests (secure vs. fast),
1 Due to limited space, we skip the details of the simpler example in Figure 2(left).

AS3 can introduce a cost tag (charging 1 unit for fast request,

and 2 unit for secure request, as a means to maximize local revenue, denoted by secure(2), fast(1)). To realize thischarging scheme, AS3, as shown at step 2, sends the policy
fragment offering the new service (with additional cost) to
AS5,AS6,AS7, respectively. After receiving these fragments
at step 3, AS5 — with no other providers available — accepts
and changes its policy to secure(2), whereas AS6 (AS7) rejects
the new offer — it was already promised a free fast route— and changes its policy to fast@4, ¬fast(1)@3. Finally, atstep 4, step 5, respectively, AS6,AS7 — to make sure they are
not charged — expose the policy fragment ¬fast(1) to its
downstream providers, the result is that AS3 will converge
to secure(2), a policy that can be practically enforced. All
the other nodes converge to a locally enforceable policy as
well, so the algorithm terminates.

3.2

Preliminary Result

Table 2: Tp represents shortest path policy (p), I1-2 show possible instances of best route selection.

We now sketch ongoing efforts towards building a policy exchange system. The main challenge is that a knowledge representation for policies that allow policies to be
distributed, while hiding information about the internal network, is not available. Prior policy aware routing schemes(like BGP and its many alternatives) embed policies in the
protocol, relying on network-specific mechanisms to express
policies. To this end, we introduce a representation systemfor policies as the key technique enabler, outline our plan
to embed the policy exchange system into the Internet routing infrastructure, and preliminary evaluation on realistic
topology.
Policy exchange as knowledge exchange. We borrowfrom the database community a powerful knowledge representation system called conditional table [3], which augments a regular table (or relation) with variables and additional conditions over those variables — a tuple is presented
only when the associated condition holds. A conditional

Flexible Routing with Policy Exchange

probability

table, depending on the evaluation of the variables and conditions, corresponds to a set of concrete instances — regular
tables with different instantiations of the variables that satisfy the condition. This makes conditional tables a naturalrepresentation for routing policies if we consider a policy
one single prescription for all possible route selection outcomes. For example, consider a routing entity 1 with twoneighbors from whom routes can be learned to a destination 0. The shortest path policy (p) of 1 can be represented
by Tp in Table 2, where Tp =A,B has two attributes: attribute
A shows whether a path is selected or not — ’r’ represents
candidate routes and ’b’ denotes best route, and attribute B
specifies the path itself. Tp contains two candidate routes asrepresented by variables x and y, and one best route x if its
associated condition holds — x is shorter than y (expressedby a function l that returns a path’s length). Observe how Tp
alone represents all possible route selection outcomes, twosuch best routes selected are shown in I1 and I2 .
More importantly, conditional table [3] can
1 comp-bgp
max-bgp
be queried with thecomp-rf
0.8
max-rfusual SQL join, projec0.6
tion, and selection etc.
0.4
in the same way as aregular table: This al0.2
lows the policy merger
0
0
2
4
6
8
(m) and fragment gentime(μs)
erator (f ) in Algorithm 1 to be formuFigure 3: The performance
lated in terms of theseof merging m (comp and max)
SQL primitives. Specifon two topologies: Rocketfuelically, since the fragtopology (rc) and topology genment of a policy (T ) areerated from BGP traces (bgp).
tuples in T that, collectively, fail to produce a best route, to compute the policy
fragment, we only need to select from T two types of tuples:(1) those tuples where (A=’b’) and whose condition evaluate
to false (the negation of which is satisfiable), and (2) tuples
where A=’r’ and whose B attributes occur in those tuplesin (1); Similarly, to merge a received policy T1 with the receiver’s current policy T2 , we only need to transform T1 into
T1′ to reflect its propagation from the origin (of T1 ) to thereceiver, followed by the union of T1′ and T2 . Ultimately, we
hope to develop a conditional table based knowledge exchange system as a means to rapid development of policy
exchange.
Integration with the routing infrastructure. In the context of BGP, to properly “install” the adjusted policies (outputof the policy exchange protocol) so that policies are enforced
during route selection, we only need to refactor those policies
into the usual BGP mechanisms, such as the local preference
attribute that overrides all other attributes during route selection to enforce preference, or (export) filters to restrict route
distribution. This translation can be achieved manually by a

APNet 2021, June 24–25, 2021, Shenzhen, China, China

human operator who has to configure BGP whether policy
exchange is used or not. However, with the introduction of aformal representation system (conditional table) of routing
policies [8], we hope to develop tools that can automaticallysynthesize those BGP configurations, so that human operators only have to understand policies in the conditional table,
without worrying about the tedious implementation in thespecific BGP mechanism.
Evaluation We implemented the merging function m (Algorithm 1 line 6-7) in policy exchange by two Python functions
comp and max: comp(p,i,t) checks whether a set of policies p
received from different neighbors are compatible with node
i’s policy in topology t. If conflict arises then i uses max(p, i, t)
to maximize the total number of admissible policies in p. In
the following, we present performance result of merging
m, and leave the development of function e and fragment
generator f as future work. All experiments were ran on
a 64-bit laptop with AMD Ryzen 7 4800H CPU and 15.4G
RAM.
We first generate
two realistic network
ps
1
2
3
0.01 46.2% 50.3% 0.35%
topologies: (1) a Rock0.05 41.4% 39.2% 19.4%
etfuel topology (AS0.1
38.7% 30.5% 30.8%7018 with 11292 nodes
0.5
29.1% 19.9% 51%
and 25382 edges); andTable
3:
Probability of satisfy(2) a topology inferreding # (1,2,3) announcements unfrom the BGP update
der different ps
file (extracted from theAS paths, has 5018
nodes and 8213 links)
from the Route View collector route-views2.oregon-ix.net,
on February 1, 2021 at 00:00 PST. We then embedded in these
two topologies the 7 nodes described in Figure 2 (right) as
follows: We randomly pick 7 nodes as AS1 to AS7; AS3 is theunique provider of AS5, it is the node at the "joint" that collects
p53 , p63 and p73 on destination d; p5 is secure policy — requires
at least one secure router fragments to the destination d;Each node in the topology is also labeled as a secure routerwith probability ps ; p6 and p7 are fast policies that require
the selected route to have a length that is below average;
When p5 conflicts with p6 and p7, we assume AS3 prioritizes
p5.
Figure 3 plots the processing time of comp and max on the
BGP topology(bgp) and Rocketfuel topology(rf). As expected,
the comp and max delays are negligible, both ≤ 8µs. Table 3
shows the number of satiable policies (as computed by max)under different ps values (1000 iterations for each ps ): as theprobability of secure routers increases from .01 to .5, theprobability of simultaneously satisfying all three policies
increases from 0.35% to 51%. We can also see that the probability of max = 2 sharply falls from 50.3% to 19.9%, which isfaster than max = 1 (from 46.2% to 29.1%). The reason is that,
intuitively, the increase of ps means that AS1 or AS2 is more
likely to satisfy p5. This illustrates how our policy merging

APNet 2021, June 24–25, 2021, Shenzhen, China, China

function can correctly recognize a maximum subset of jointly
satisfiable policy fragments.

4

LIMITATIONSPolicy exchange does not magically remove all policy issues. In particular, policy exchange does not detect (resolve)
conflicts among local policies, nor does it move policy enforcement to the most fitting location when scalability isconcerned.
Conflicting policies and route oscillation. It is well known
that routing policies can conflict and cause the routing system to oscillate permanently [6, 12, 14, 16, 17, 28, 35]. For
example, three ASes connected in a circle with (clock-wise)
cyclic preferences — each AS prefers path via its clock-wiseneighbor than its direct path — have conflicting policies thatcause permanent oscillation. Policy exchange cannot address
such conflicts: the cyclic preference at each AS are perfectly
local, none of the ASes has a policy fragment to start an exchange. Moreover, policy exchange only improves visibility
into the concerns that cannot be addressed within an AS.
Besides, even when a policy fragment received by a routing
entity conflicts with its local policy, the receiving entity canstill ignore it. Generally, policy exchange neither detects nor
resolves conflicts among independently set policies.
Policy holes and routing scalability. Address aggregation in the CIDR routing structure, till today, remains one of
the main vehicles to scalability, but policy can punch a holein the aggregate and drastically drive up the routing tablesize [18, 30]. For example, a more specific prefix (d1 ) of an
existing aggregate (d), owned by AS1, can be announced totwo different links (l1,l2). This implements a useful trafficengineering policy at AS1 that balances traffic received at
l1,l2. At the same time, d1 will be propagated throughout
the Internet, unnecessarily creating routing entries for d1 everywhere. Policy exchange can mitigate this problem, but
only partially: Suppose AS1 sends the load balancing restriction that traffic cannot exceed a threshold on each link. This
restriction, when received at some upstream AS2 that is on
all the paths to d, will be determined to be locally enforceable. Hence it will be kept local at AS2, and suppressed fromfurther populating the rest of the Internet. However, AS1 may
not trust AS2, or simply lacks the incentive to start policy
exchange with AS2.
While policy exchange does not directly solve the above
problems, its building blocks — the new policy representation system, the decoupling of policy from routing — may
migrate to new solutions beyond flexible routing, and may
clarify and simplify the interaction between policy and othercomponents of the routing system.

5

RELATED WORKPolicy distribution. Existing inter-domain routing schemes
often employ some forms of policy distribution: In the MIRO [36]Bin Gui, Fangping Lan, Anduo Wang

system, a participant can pull neighbors for alternative routes
satisfying a particular need. In BGP, restricted form of policy information disclosure is also available with MED [29]attribute and the community attribute [21]. More recently,
a BGP extension for policy distribution [22] that enhances
community attribute based policy tagging and negotiation
was also proposed. Our work attempts to generalize these
efforts: policy exchange systematically coordinates policies
on the fly, it does not require pre-mediated agreement, andis not restricted to a specific scheme tailored to a particulartask.
Declarative networking. In the context of database usages
in networking, we are the closest to declarative networking [9, 10, 23–27] which introduces network datalog — adata query language reminiscent of SQL — as a compact andefficient language for expressing networking such as routing protocols and overlay networks. Our work goes beyond
programming with factual data. To our best knowledge, weare the first to investigate the use of indefinite data (i.e. conditional tables) to lift policies (intentions) to first order datathat can be queried and transformed.

6

CONCLUSION

This paper made the case of policy exchange as a means toaccommodate distributed policies in the absence of a central
authority. Policy exchange instantiates a simple principlethat a policy should be permitted as long as it poses noharm to others, realized in a way that minimizes information
disclosure. This makes policy exchange a possible solution to
the longstanding policy routing problem in the Internet. We
present a preliminary design and ongoing efforts towards apractical policy exchange system. While making any changes
to the Internet infrastructure has proven to be extremely
difficult, we believe that a deeper understanding of the limitof distributed policy making is needed. We also hope that,with some luck, our knowledge powered technique enablers
may infect the design and migrate into the fabric of the future
routing system.
Acknowledgments. This work is supported by the National
Science Foundation Award CNS-1909450.

REFERENCES[1] 1989. Policy requirements for inter Administrative Domain routing.
RFC 1125. https://doi.org/10.17487/RFC1125[2] 1989. Policy routing in Internet protocols. RFC 1102. https://doi.org/
10.17487/RFC1102[3] Serge Abiteboul, Richard Hull, and Victor Vianu (Eds.). 1995. Foundations of Databases: The Logical Level (1st ed.). Addison-Wesley Longman
Publishing Co., Inc., Boston, MA, USA.
[4] Serge Abiteboul, Paris Kanellakis, and Gosta Grahne. 1987. On the
Representation and Querying of Sets of Possible Worlds. In Proceedingsof the 1987 ACM SIGMOD International Conference on Management of
Data (San Francisco, California, USA) (SIGMOD ’87). Association for
Computing Machinery, New York, NY, USA, 34–48. https://doi.org/
10.1145/38713.38724

Flexible Routing with Policy Exchange[5] Katerina Argyraki and David R. Cheriton. 2004. Loose Source Routing
as a Mechanism for Traffic Policies. In Proceedings of the ACM SIGCOMM Workshop on Future Directions in Network Architecture (Portland, Oregon, USA) (FDNA ’04). Association for Computing Machinery,
New York, NY, USA, 57–64. https://doi.org/10.1145/1016707.1016718[6] Anindya Basu, Chih-Hao Luke Ong, April Rasala, F. Bruce Shepherd,
and Gordon Wilfong. 2002. Route oscillations in I-BGP with routereflection. In Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications (Pittsburgh, Pennsylvania, USA) (SIGCOMM ’02). ACM, New York, NY, USA,
235–247. https://doi.org/10.1145/633025.633048[7] Hans-Werner Braun. 1989. Models of policy based routing. RFC 1104.
https://doi.org/10.17487/RFC1104[8] M. Caesar and J. Rexford. 2005. BGP Routing Policies in ISP Networks.
Netwrk. Mag. of Global Internetwkg. 19, 6 (Nov. 2005), 5–11. https://doi.org/10.1109/MNET.2005.1541715[9] Xu Chen, Z. Morley Mao, and Jacobus van der Merwe. 2007. Towards Automated Network Management: Network Operations Using
Dynamic Views. In Proceedings of the 2007 SIGCOMM Workshop on
Internet Network Management (Kyoto, Japan) (INM ’07). ACM, New
York, NY, USA, 242–247. https://doi.org/10.1145/1321753.1321757[10] Tyson Condie, Joseph M. Hellerstein, Petros Maniatis, Sean Rhea, andTimothy Roscoe. 2005. Finally, a use for componentized transport
protocols. In In HotNets IV.
[11] Deborah Estrin and Martha Steenstrup. 1991. Inter Domain Policy
Routing: Overview of Architecture and Protocols. SIGCOMM Comput.
Commun. Rev. 21, 1 (Jan. 1991), 71–78. https://doi.org/10.1145/116030.
116036[12] Nick Feamster, Ramesh Johari, and Hari Balakrishnan. 2007. Implications of Autonomy for the Expressiveness of Policy Routing. IEEE/ACM
Trans. Netw. 15, 6 (Dec. 2007), 1266–1279. https://doi.org/10.1109/
TNET.2007.896531[13] Igor Ganichev, Bin Dai, P. Brighten Godfrey, and Scott Shenker. 2010.
YAMR: Yet Another Multipath Routing Protocol. SIGCOMM Comput.
Commun. Rev. 40, 5 (Oct. 2010), 13–19. https://doi.org/10.1145/1880153.
1880156[14] Lixin Gao and Jennifer Rexford. 2000. Stable Internet routing without
global coordination. In ACM SIGMETRICS.
[15] P. Brighten Godfrey, Igor Ganichev, Scott Shenker, and Ion Stoica. 2009.
Pathlet routing. In ACM SIGCOMM.
[16] Timothy G. Griffin, F. Bruce Shepherd, and Gordon Wilfong. 2002.
The Stable Paths Problem and Interdomain Routing. IEEE Trans. on
Networking 10 (2002), 232–243.
[17] Timothy G. Griffin and Gordon Wilfong. 1999. An Analysis of BGP
Convergence Properties. In SIGCOMM.
[18] Geoff Huston. 2001. Commentary on Inter-Domain Routing in theInternet. RFC 3221. https://doi.org/10.17487/RFC3221[19] Tomasz Imieliundefinedski and Witold Lipski. 1984. Incomplete Information in Relational Databases. J. ACM 31, 4 (Sept. 1984), 761–791.
https://doi.org/10.1145/1634.1886[20] H. Tahilramani Kaur, S. Kalyanaraman, A. Weiss, S. Kanwar, and A.
Gandhi. 2003. BANANAS: An Evolutionary Framework for Explicit
and Multipath Routing in the Internet. In Proceedings of the ACM SIGCOMM Workshop on Future Directions in Network Architecture (Karlsruhe, Germany) (FDNA ’03). Association for Computing Machinery,
New York, NY, USA, 277–288. https://doi.org/10.1145/944759.944766[21] Tony Li, Ravi Chandra, and Paul S. Traina. 1996. BGP Communities
Attribute. RFC 1997. https://doi.org/10.17487/RFC1997

APNet 2021, June 24–25, 2021, Shenzhen, China, China[22] Zhenbin Li, Liang Ou, Yujia Luo, Sujian Lu, Huaimo Chen, Shunwan
Zhuang, and Haibo Wang. 2020. BGP Extensions for Routing Policy
Distribution (RPD). Internet-Draft draft-ietf-idr-rpd-05. Internet Engineering Task Force. https://datatracker.ietf.org/doc/html/draft-ietfidr-rpd-05 Work in Progress.
[23] Changbin Liu, Boon Thau Loo, and Yun Mao. 2011. Declarative Automated Cloud Resource Orchestration. In Proceedings of the 2Nd ACM
Symposium on Cloud Computing (Cascais, Portugal) (SOCC ’11). ACM,
New York, NY, USA, Article 26, 8 pages. https://doi.org/10.1145/
2038916.2038942[24] Changbin Liu, Lu Ren, Boon Thau Loo, Yun Mao, and Prithwish Basu.
2012. Cologne: A Declarative Distributed Constraint Optimization
Platform. Proc. VLDB Endow. 5, 8 (April 2012), 752–763. https://doi.
org/10.14778/2212351.2212357[25] Boon Thau Loo, Tyson Condie, Minos Garofalakis, David E. Gay,
Joseph M. Hellerstein, Petros Maniatis, Raghu Ramakrishnan, Timothy Roscoe, and Ion Stoica. 2006. Declarative Networking: Language, Execution and Optimization. In Proceedings of the 2006 ACM
SIGMOD International Conference on Management of Data (Chicago,
IL, USA) (SIGMOD ’06). ACM, New York, NY, USA, 97–108. https://doi.org/10.1145/1142473.1142485[26] Boon Thau Loo, Joseph M. Hellerstein, Ion Stoica, and Raghu Ramakrishnan. 2005. Declarative Routing: Extensible Routing with Declarative Queries (SIGCOMM ’05). ACM, 12 pages. https://doi.org/10.1145/
1080091.1080126[27] Yun Mao, Boon Thau Loo, Zachary Ives, and Jonathan M. Smith. 2008.
MOSAIC: Unified Declarative Platform for Dynamic Overlay Composition. In Proceedings of the 2008 ACM CoNEXT Conference (Madrid,
Spain) (CoNEXT ’08). ACM, New York, NY, USA, Article 5, 12 pages.
https://doi.org/10.1145/1544012.1544017[28] D. McPherson, V. Gill, D. Walton, and A. Retana. RFC 3345, 2002. Border
Gateway Protocol (BGP) Persistent Route Oscillation Condition. (RFC
3345, 2002).
[29] Danny R. McPherson and Vijay Gill. 2006. BGP MULTI_EXIT_DISC(MED) Considerations. RFC 4451. https://doi.org/10.17487/RFC4451[30] B. Quoitin, C. Pelsser, L. Swinnen, O. Bonaventure, and S. Uhlig. 2003.
Interdomain Traffic Engineering with BGP. Comm. Mag. 41, 5 (May2003), 122–128. https://doi.org/10.1109/MCOM.2003.1200112[31] Yakov Rekhter, Steven Hotz, and Dr. Deborah Estrin. 1992. A Unified
Approach to Inter-Domain Routing. RFC 1322. https://doi.org/10.
17487/RFC1322[32] Y. Rekhter, T Li, and S Hares. 2006. A Border Gateway Protocol 4 (BGP-4).
RFC 4271. RFC Editor. http://www.rfc-editor.org/rfc/rfc4271.txt[33] Arun Seehra, Jad Naous, Michael Walfish, David Mazières, Antonio
Nicolosi, and Scott Shenker. 2009. A Policy Framework for the FutureInternet. In In Proc. HotNets.
[34] Martha E. Steenstrup. 1993. An Architecture for Inter-Domain Policy
Routing. RFC 1478. https://doi.org/10.17487/RFC1478[35] Kannan Varadhan, Ramesh Govindan, and Deborah Estrin. 2000. Persistent route oscillations in inter-domain routing. Computer Networks
32, 1 (2000), 1 – 16. https://doi.org/10.1016/S1389-1286(99)00108-5[36] Wen Xu and Jennifer Rexford. 2006. MIRO: Multi-path interdomain
routing. In ACM SIGCOMM.
[37] Xiaowei Yang, David Clark, and Arthur W. Berger. 2007. NIRA: a newinter-domain routing architecture. IEEE/ACM Trans. Netw. 15, 4 (2007).
[38] Dapeng Zhu, Mark Gritter, and David R. Cheriton. 2003. Feedback
Based Routing. SIGCOMM Comput. Commun. Rev. 33, 1 (Jan. 2003),
71–76. https://doi.org/10.1145/774763.774774