BGP

• compromised of independent networks:

• AS of different types

• ISPs offering transit (e.g. Telekom, Vodafone)

• Campus Netowks (organisations maintaining networks at one or more locaionts -> universities, companies)

• datacenter networks (operated by large IT companies e.g. Facebook and hosting providers e.g. Amazon AWS)

• content delivery networks (e.g. akamai, google, cloudflare)

• zero, one, more…

• some local

• some worldwide

• Routing protocols find a path towards a destination and allow to create Forwarding tables

• Routers use Forwarding tables for per-packet lookup to determine outgoing interface

• border router

  • connect different ASes

• core router

  • routers inside AS

  • and in core of internet (middle of interent…)

• edge router

  • close to edge of internet (not rally many AS around…)

• transit AS

  • forward traffic from one AS to another

• Stub AS

  • AS which is connected to only one other AS

• Multi-Homed AS

  • AS which is connected to multiple AS

  • doen’t forward traffic on their behalf

• inter domain protocol (inter AS routing)

  • exchange routing info between ASes

  • -> called Exterior Gateway Protocol

  • => de facto only BGPv4 used

• intra domain routing

  • used to determine path and routing info INSIDE an AS

  • -> called interior gateway protocol

  • examples: OSPF, RIP

• EGP: which AS to transfer packet to?

• IGP: which intra-AS route to use to reach this neighboring AS? (also if end AS -> where to deliver packet to…)

• all routing inforamtion a router can gather from updated of neighboring routers

• may contain multiple routes to the same destination

• path selection also depends on business considerations (policy routing)

• mapping from destinatino IP network address (prefix) to outgoing interface or next hop router IP address -> effectively the routing table…

• UNIQUE entry for EACH destination

• use longest-prefix matching (LPM)

• algorithm uses FIB to decide how to forward individual packets

• RIB: all available infromation

• -> apply routing algorithm

• FIB -> has best path to destinatinos, based on RIB (routing table)

• -> use to make forwarding decisions by lookup (LPM)

• internal destioatnios -> only intra-AS

• external destinations -> inter-AS AND intra-AS

• receiving packet from other AS

• -> to which other border router should the packet be forwarded to?

• => needs to learn which destinaitons are reachable via other AS

• -> propagate reachability info to all routers within AS

• border router learns that an AS is only reachable via AS2

• -> propagates this information to the internal routers…

• -> internal (core) routers use this information and calculate shortest path to gateway router to AS2 and put corresponding interface entry into their routing table…

• -> multiple optoins

• -> inter-AS decides best path (via which AS should it go…)

• -> and then again propagate informaiton (not task of internal routers… -> they only get one option basically…)

• inter AS:

  • onyl for destiation outside of own AS

  • used to determine gateway router

  • also: steer traffic from one as to another via own…

• intra-AS:

  • used for destinations within own AS

  • used to reach gateway routers for outside destinations

• each AS has unique AS number

• path vector

• business decision…

• -> policy based

• contains all ASes on the path towards the destination…

• => allows loop detecion…

• iBGP (internal bgp)

  • BGP exchanges information with routers in the same AS

• eBGP (external BGP)

  • BGP exchanges information with routers of neighboring ASes

• gets allocated portion of provider ISPs address space…

• efficient advertisement fo routing information

• -> e.g. ISP has /32

• -> announces that it takes all for /32

• -> forwards it to its clients (organizations with AS) that got part of the ISPs address space…

• -> other ISP announces more specific if it has better route…

• iBGP:

  • both routers have the same ASN

  • propagates also informaiton on externally reachable pefixes to routers within AS

• eBGP

  • routers have different ASNs

• TCP

• OPEN

  • opens connection between two routers

• TEARDOWN

  • close the connection

• NOTIFICATION

  • send error codes

• UPDATE

  • announce new route, or un-reachability of an old one

• destination prefix

• AS path (list of ASes taht have to be traversed)

• next hop (IP address of router sending the update)

• origin (from what protocol is it learned ? via IGP/EGP/other)

• optional:

  • Local Preference (prefer one gateway over anotehr)

  • multi exit discriminator (if multiple entries into an AS exist (i.e. multiple border routers to that AS) -> says which is prefferred)

• each announcing AS prepends its own ASN to it…

• no -> local informatoin (preference) has influence…

1. local preference value attribute : policy decision

2. shortest AS_PATH

3. closest NEXT-HOP routers outside AS : hot potato routing

4. additional criteria (e.g. lowest MED when different border routers to same neighboring AS exist…)

• always hand traffic over as fast as possible…

• -> the longer the packet is transferred INSIDE an AS, the more it costs

• => choosing nearest connection site minimizes cost

• => leads to assymetric routing…

=> e.g. german people:

• drive from iffezheim to straßbourg on german side until very close

=> french people:

• drive on alsace site until i.e. wintersdorf…

• private -> direct connection to (frequently large) AS

• public: exchanging traffic with other ASes at an IXP

peering:

• two ASes peer -> if have kind of BGP relationship (i.e. two ASes directly connected)

• -> protocol viewpoint: irrelevant if one party pays the other party

• -> alternative viewpoint (policy viewpoint) : arrowly peering implies there is no financial compensation…

=> can be establised

• lengthy contracts

• sysadmins talking with each other

• install cable from server room of AS1 to server room of AS2

• use colocation center operated by carrier neutral data center provider

• peering at coloation center operated by carrier

• exchange large amount of traffic with single AS

• attractive setup for upstream providers

• interconnection of, within and inbetween datacenters

• use peering locaiton

• -> switch in middle

• -> allow to connect to lots of ASes

• => payment per switch port, priced by connection speed…

• peer with as many ASes as possible…

• reduce traffic you send to your upstream provider…

1. route via customer (financial gain)

2. route via peer (no financial gain or loss)

3. route via provider (financial loss)

=> announce routers that incur financial gain (used by customers…)

=> announce routes that reduce costs if peers use them

=> do not announce ruots that incur financial loss (as long as alternative path exists)

• provider AS announces routes for reaching the whole internet to customer AS…

• -> customer AS announces routes for reaching its prefixes to provider AS

• => the more traffic the customer sends to the provider or receives from the provider -> the more money the provier makes…

=> customer relationship indicated with

customer -> provider

=> multi-homed: several providers

• several AS announce routes for reaching whole internet

• customer announces own prefixes to ASes

• the mroe traffic exchange with a provdier -> the mroe money it makes

• => customer chooses cheapest / best quality provider

• => customer only announces own prefixes to the chosen providers..

• => if announce other prefixes, provider will route over it (-> no benefit, only financial loss…)

  
  

• adding his AS number several time to path in BGP announcement

• provider tells customer all rotues

• customer anounces its own stuff

• customer anounces to the one with better price /quality

• wont announce other prefixes -> onyl cost due to proviers routing throuth it

• may announce to not chosen one (to have additional route possible) but prepends own ASN multple tome to increase AS PATH

• All announce from their customer

• -> intermediate pays provider for traffic from customer

• -> but also gets money from customer…

• provider tells peer about own prefixes and customers

• -> no cost but gain from customer

1. upstream: sequence of customer -> provide links

2. peering

3. downstream: provider -> customer

• sibliung = mutual transit agreement

• => provide connectivity to rest of internet for each other

• => very extensive peering…

• two small ASes close to each other that cannot / do not want to afford additional interenet services

• merging of two companies

  • merging two AS difficult

  • -> simply peering and exhcnage everything -> easy

  
  

• differnet levels of providers

• Tier1 (default free zone): only peering, no providers

• TIer 2: only peerings and one or more Tier 1 provider

• Tier 3: at least one tier 2 as provider

• Tier n: at least one tier n-1 provier

• tier 1.5 -> almost tier 1 but pays for some links

• AT&T

• deutsche telekom AG

• Sprint

• Verizon

• KPN International

• select path that incurs most money

• special / political consideratoins (e.g. not through russia…)

export only

1. if it incurs money

2. if it reduces cost

3. if it is inevitable

• number of direct and indirect customerrs

• alternative: k-core algo

• k-core -> minimal number of edger per node

• => i.e. if every node has a connection -> 1-core …

• get 2-core:

  • remove all nodes of degree <= 1 recursively

  • did you remove any node?

    • yes: goto step 1

    • no: return

• => resutls in 2-core

• => 3-core: take 2-core and recusrively remove nodes of degree <= 2…