I'm trying to program a simplified version of a eBGP speaker. For the import policy, I want to make sure that any new route that I import doesn't have any loops. The routing table that I build looks something like this.
10.0.0.0/8 3 8 11
10.8.0.0/8 4
192.168.0.0/16 3 5 6
192.168.43.0/24 (local)
My question is, how do you check for a routing loop?
Now I've tried multiple things and I think the right way to see if there would be any loops would be to construct a DAG using all the routes in the routing table. Then checking if the new route creates a cycle in the graph. But I can't understand if I should only look at certain prefixes when creating the DAG.
In eBGP loop detection is based on the ASPATH. You can NOT accept routes with ASPATHs that include your own ASN.
This is defined in RFC4271:
If the AS_PATH attribute of a BGP route contains an AS loop, the BGP route should be excluded from the Phase 2 decision function. AS loop detection is done by scanning the full AS path (as specified in the AS_PATH attribute), and checking that the autonomous system number of the local system does not appear in the AS path. Operations of a BGP speaker that is configured to accept routes with its own autonomous system number in the AS path are outside the scope of this document.
Hint: If you want to implement a BGP Speaker, I suggest your meticulously read all related RFCs starting with RFC4271.
As for iBGP there is no loop detection needs as an iBGP Speaker will NOT forward iBGP learned routes to another iBGP speaker. You need to have all your iBGP speaker connected in full-mesh, use a route-reflector or confederations.
Article regarding those principles (for iBGP): http://www.rogerperkin.co.uk/routing-protocols/bgp/bgp-confederation-vs-route-reflector/