PEMP-Quagga is an open source project implementing PEMP routing in the Quagga routing daemon.
With Peering Equilibrium MultiPath (PEMP) routing, two neighboring Autonomous System (AS) networks can agree in coordinating the routing between some of their destination cones, i.e., their destination prefixes (own or customers’) or a subset of them. In other words, the routing of the traffic between some of their BGP communities can be isolated and differently managed so that it follows a specific policy routing defined by a game-theoretic logic.
The goal of the game-theoretic policy is to avoid tie-breaking BGP routing and to decrease the bilateral routing inefficiency lead by early-exit (hot-potato) routing, by making use of multipath routing with strategic load-balancing over the interconnection links. For this purpose, the multi-exit-distriminator (MED) field is used as a signaling channel to exchange IGP transit path costs. In practice, the PEMP routing coordination framework can reinforce existing peering settlements, by ensuring stability to routing across peering links, while also supporting peering link congestion management (if needed). More theoretical and practical information can be found in References [1] and [2]. An introduction is given in PEMP: a quick introduction.
HOW TO INSTALL
1> Download the software
From github https://github.com/routing-games
2> Pre installation check
* To be fully functional, we recommend to install PEMP-Quagga on a Linux platform (support for multipath and policy based routing is needed). It has been developed and tested under Ubuntu 14.04.2 with Linux kernel 3.16.
* Texinfo, gwak and automake are prerequisite packages that need to be installed
sudo apt-get install gawk
sudo apt-get install texinfo
sudo apt-get install automake
3> Configuration
* Turn on multipath routing support
./configure –enable-multipath=0
* Force Quagga router to use GNU/Linux netlink interface for communicating with the kernel
./configure –enable-netlink
* Enable Quagga to run as root (optional)
./configure –enable-user=root
./configure –enable-group=root
4> Installation
Install the RGL: instructions here.
make install
ONCE INSTALLED: HOW TO CONFIGURE
* To enable PEMP’s supporting features in Quagga, you need to include the following line in BGP and OSPF configuration files.
By default, the configuration files of BGP and OSPF are located at:
/usr/local/etc/bgpd.conf,
/usr/local/etc/ospfd.conf.
1> BGP configuration
router bgp <ASN>
bgp router-id <IP ADDRESS>
bgp bestpath as-path multipath-relax
maximum-paths ibgp <NUMBER OF PATH>
redistribute ospf
neighbor <IP ADDRESS> remote-as <ASN>
neighbor <IP ADDRESS> remote-as <ASN>
neighbor <IP ADDRESS> remote-as <ASN>
pemp enable
routing-game community local-id <COMMUNITY ID> peer-id <COMMUNITY ID> configure <COORDINATION POLICY> <POTENTIAL THRESHOLD> <USE LOAD BALANCING>
local network <PREFIX> community <LOCAL COMMUNITY ID>
peer network <PREFIX> community <PEER COMMUNITY ID>
bgp bestpath as-path multipath-relax
Enable bgpd to support multipath routing for inter domain traffic. By default, Quagga router does not enable BGP multipath routing,
we need to turn on this feature on the configuration file.
maximum-paths ibgp <NUMBER OF PATH>
Specify the maximum number of multipath support
redistribute ospf
Allow IGP path cost distribution from the intra domain routing protocol (in this case is ospfd) to bgpd
PEMP commands:
pemp enable
Enable peering equilibrium multipath routing support
routing-game community local-id <local community id> peer-id <peer community id> configure <coordination policy> <potential threshold> <load balancing>
Establish a routing game with peering AS for traffic flow from the its local community to peer’s community, this flow is defined by the pair of
community ID and peer community ID. Community is a group of network prefixes that would like to receive same routing decision made by PEMP,
and each community is identified by a unique community ID. The command above also help to initializes the game with input parameters specifying
coordination policy being used, the value of potential threshold as well as load balancing mode. These parameters are specified after the “configure” command.
By issuing this command, any packets from the local community id destined to the peer community id will be routed according to PEMP.
<local community id> accepts any integer numbers that greater than 0 as its value, the number is defined by the local AS with agreement from peering AS
<peer community id> accepts any integer numbers that greater than 0 as its value, the number is defined by the peering AS with agreement from local AS to avoid duplication
<coordination policy> is integer number in the range from 0 to 3, in which
0: Nash equilibrium multipath (NEMP)
1: Pareto-frontier
2: Pareto-jump
3: Unselfish jump
<potential threshold> is any real numbers that greater than or equal 0
<load balancing> only accepts 0 or 1 as its value, in which
0: Equal load balancing
1: Enable sub flow load balancing
* NOTE: flow configuration must be the same at both peer, peers must agree on the same set of community ID used and the game parameters for each
defined flow in both sides must be the same
2> OSPF configuration
border router-id <border router’s IP address>
Enable IGP path cost calculation for the path between PEMP enable router and specified border router. If we do not specify the IP address of egress router here,
the IGP path cost value of this router could not be calculated and it would not be considered as an option in the routing game.
3> Example
* Scenario: AS 6002 interconnects with AS 6004 via three peering links. Within AS 6002, router RA (192.168.2.4) connects directly with network A (192.168.2.0/24),and learns
three different egress routers RA1 (192.168.1.6), RA2 (192.168.4.6), and RA3 (192.168.5.6) to forward traffic from A to any external networks advertised by AS 6004. Within
AS 6004, router RB (192.168.3.2) connects directly with network B (192.168.3.0/24), and learns three different egress routers RB1 (192.168.21.6), RB2 (192.168.24.6), and
RB3 (192.168.25.6) to send traffic from A to any external networks advertised by AS 6002. AS 6002 would like makes a peering agreement with AS 6004, in which both peers agree
that traffic between network A in 6002 and network B in 6004 is sensitive to delay and it deserves carefully routing. Beside that the amount of traffic that A sends to B is
also quite similar to the amount of traffic sent from B to A. Network operators decide to enable peering equilibrium multipath routing for traffic between A and B.
To do so peers need to reload router RA and RB with new PEMP supporting configuration. The new configuration files are presented as follow:
+ A snapshot of BGP configuration file in router RA of AS 6002
router bgp 6002
bgp router-id 192.168.2.4
bgp bestpath as-path multipath-relax
maximum-paths 3
maximum-paths ibgp 3
redistribute ospf
neighbor 192.168.1.6 remote-as 6002
neighbor 192.168.4.6 remote-as 6002
neighbor 192.168.5.6 remote-as 6002
pemp enable
routing-game community local-id 2 peer-id 3 configure 1 2 1
local network 192.168.2.0/24 community 2
peer network 192.168.3.0/24 community 3
+ A snapshot of OSPF configuration file in router RA of AS 6002
router ospf
ospf router-id 192.168.2.4
border router-id 192.168.1.6
border router-id 192.168.4.6
border router-id 192.168.5.6
network 192.168.1.0/24 area 0.0.0.0
network 192.168.2.0/24 area 0.0.0.0
network 192.168.4.0/24 area 0.0.0.0
network 192.168.5.0/24 area 0.0.0.0
+ A snapshot of BGP configuration file in router RB of AS 6004
router bgp 6004
bgp router-id 192.168.3.2
bgp bestpath as-path multipath-relax
maximum-paths 3
maximum-paths ibgp 3
redistribute ospf
neighbor 192.168.21.6 remote-as 6004
neighbor 192.168.24.6 remote-as 6004
neighbor 192.168.25.6 remote-as 6004
pemp enable
routing-game community local-id 3 peer-id 2 configure 1 2 1
local network 192.168.3.0/24 community 3
peer network 192.168.2.0/24 community 2
+ A snapshot of OSPF configuration file in router RB of AS 6004
router ospf
ospf router-id 192.168.3.2
border router-id 192.168.21.6
border router-id 192.168.24.6
border router-id 192.168.25.6
network 192.168.3.0/24 area 0.0.0.0
network 192.168.21.0/24 area 0.0.0.0
network 192.168.24.0/24 area 0.0.0.0
network 192.168.25.0/24 area 0.0.0.0
HOW TO RUN
* Routing decision in PEMP relies on the interactions between BGP and an underlying interior gateway protocol such as OSPF, so it requires
the execution of both bgpd and ospfd daemon. Zebra updates kernel routing table and it is mandatory to run ospfd.
Therefore a minimum sequence for running a PEMP enable router is
# zebra -d
# ospfd -d
# bgpd -d
* The result of PEMP routing decision is recorded in a log file with name formated as “routing_game” followed by “HH:MM:AM/PM” which indicates
the point of time routing game is built and decision is made.
REFERENCE
[1] Stefano Secci et al, “Peering Equilibrium Multipath Routing: A Game Theory Framework for Internet Peering Settlements“, IEEE/ACM Transactions on Networking, Vol. 19, No. 2, pp: 419-432, April 2011.
[2] Duy NGUYEN, Stefano SECCI, “Equilibrium Routing: from Theory to Practice“, Proc. of 23rd Int. Conference on Telecommunications (ICT 2016)