Dynamic Routing

• routing: process of chosing optimal path for a packet

• forwarding: actually delivering the packet to the right interface

• on the routing table

• => e.g. Longest prefix matching

• => find row with next hop that determines the forward decision

  
  

• routes remain until you manually change them

• -> manual effort

• -> can be cause of error

• -> always has to manually adjust if changes in topology … occur

• => not applicaple to large scale network…

• network uses dynamic routing protocols

• -> audomatically identify optimal routes between nodes of the network…

• -> old routes will be updated in routing table…

• -> allows to take topology changes, busy links and routing policies into consideration…

• => dynamically adapt to environment

• dyn: workload router increases, workload admin decreases

• stat: workload router decreases, workload admin increases

• router requires extended overview over network

• -> exchanging and processing routing informaiton messages

• content

• transmission range

• impact

• use some sort of metric to determine optimal paths

• bets path => path with best metric (usually lowest e.g. cost)

• path length

• reliablility

• delay

• bandwidth

• load

• static vs dynamic

• single-path vs multi-path

  • multi -> allow more than one path to a destination -> can lead to better throughput and reliability

• flat vs hierarchical

• intradomain vs interdomain

  • some only work in subnets (such as diff. AD; while others are utilized between them e.g. BGP)

• link-state vs distance-vector

  
  

• link state:

  • broadcast routing inforamtion within network

• distance vector

  • exchange routing info only with direct neighbors

• routing

• fowarding

  
  

• determine next hop for each destination address

• triggered by a change in network topology, out -of-band

• => build routing informatino base (routing table)

• => part of devices control plane

• transferring data packet from incoming to outgoing link

• triggered by incoming packet, time-critical

• => access forwarding information base

• => part of devices data plane

• decentralized network of networks

• many organizations operate their own network -> which all need to be interconnected

• => glue: IP protocol, exchange of routing inforamtion with BGP

• content providers

  • content delivery nodes CDN support content providers

  • e.g. netflix, dropbox, twitter,…

• access providesr (eyeball networks); content consumption

• transit providers

• exchange point for traffic between network operators

• -> makes iteasy to connect to many other networks (via peering)

• provides phyiscal infrastructure

=> ISP, CDN, … connect with each other here…

• DE-CIX -> Frankfurt

• AMS-IX -> amsterdam

• LINX -> London

• neworks under a common administrative organization

  • e.g. IPS, camous network

• uniquely identified by a 32bit AS-number

• each AS advertises the address space it is willing to acccept (belonging to the AS itself or as transit traffic)

• 
  

• single entity with border routers and routed address space

  
  

• No! -> AS simply accepts specific IP address range -> does the rest itself once the packets arrived…

• => uses intra-AS routing for this…

• inter-AS routing

• => all AS must aggree on common way of exchanging routing information!!

• => BGP

• inter-AS

  • take business policies into consideratoin more so than finding best paths

  • => different link metrics and filtering policies (e.g. one link more expensive due to other business contracts…)

• intra AS

  • find best path

• yes! -> lots of entries

• e.g. IPv4 ~ 800k entries

• IPv6 ~ 60k entries

static:

• manual construction of routing table

• does not scale

• does not react to changes

dynamic:

• distributed algos automate construction of routing table

• scales depending on the algo

• automated routing tbale updates after topology changes (within a certain delay)

• => distributed algos automate construction of routing tables

• scales depending on algo

• automated ru

• find a path from the source to the destination host

• => can be reduced to graph problem

• nodes represent router

• edge represents link

• link coms with certain cost c(X,Y)

1. gather informaiton about network topology

2. create local routin table based on gathered information

• OSPF (link state)

• RIP (distance-vector routing)

• BGP (path-vector routing)

• each roputer exchanges link state updates with each other router in the network (flooding)

• link state updtates contain list of ajacent routers and networks incuding cost

• => each router knows whole network topology

• each ruter calculates shortest poaths to every other destination (e.g. using dijkstra)

• derive routing table from shortest path tree

• each router exhanges advertisements with its neighbor

• advertisements contain shanpshot of current routing table (as distance vectors) of source (neighboring) router

• => routers have limited information baout network topology (locla view / only neighbor)

  
  

• each router keeps distance vectors to all other routers

• compute new distance vector on incoming advertisement

• derive routing table from distance vectors

• e.g. RIP, BGP (path vector)

• link state: e.g. dijkstra

• distance vector: bellman ford

• distance vector (poisoned reverse)

  • if shortest path to dest Y was learned from neighbor Z => set distance to Y to infinite for the uptades to neighbor Z

• path vector routing

  • update messages contain full paths

  • => allows loop-detection

    
    

scalability:

• LS floods network

• DV nodes only talk to neighbors

speed of convergence

• LS converges fast

• DV can converge slowly (e..g count to infinity problem, routing loops may occur temporarily)

• Routing information protocol

• RIPv2, RIPng (supports IPv6)

• interior gateway protocol (IGP)

• distance vector algo

• link metric: number of hops (link cost = 1; infinity = 16)

• implements poisoned reverse

• UDP port 520

• RIP response messages send periodically (every 30s) or on changes

• link is declared unreachable after 180s without an update

• each advertisement contains routers to max. 25 destinations

• open shortest path first

• conceived as successor to RIP

• OSPFv3 adds support for IPv6

• interior gateway protocol (IGP)

• link state algo

• multiple same cost paths

• supports hierarchy through definition of areas

  
  

• UP datagrams with protocol number 89, multicast addreessing

• messages can be authenticated

• border gateway protocol

• de facto standard inter-AS routing protocol in the internet

• BGPv4 introduced in 1994

• extensible to implement new functions

• built to scale

• implements policy-based routing

• path vector algo (path is sequence of AS numbers)

• uses periodic keepalives and incremental updates

• TCP port 179

• eBGP spreads inter-AS routing information between ASes

• iBGP spreads inter-AS routing information

  What does the router do for routing within ASes

• path is sequence of AS numbers

• routing table growth (>800.000 IPv4 entries)

• load balancing in multi-homed ASes

• security: BGP prefix hijacking

• commonly, link state converges more quickly that distance vector

• link state floods network with routing information and requests state of the links of routers

• distance vector only interested in which neighbors they are connected to

• link state -> every router knows everything about network

• distacnce vector -> router only have local view of network

positive:

• automatically adapt to perceptible changes in network

• can - in general - be applied independent of network size

negative:

• routing loops still can happen (due to the complexity of networks, often even not full understood why routing loop happens)

• dynamic routing has delay -> no immediate updates

• still require manual intervention

• more secure in terms of resilience against evildoers

• less workload for involved routers

• static routin easier to implement in small networks

• no routing message overhead

• yes -> trigger updates outside of regular updates…

• no -> update information is more an order than an suggestion…

• sth changes -> router sends update to neighbors

• -> neighbors integrate infmraotn and update routing table

• -> immediately propagate information to their neigbors

• no -> keep only best…

• implement max hop count of 15

• -> hop count of 16 indicates that the cost (distance) is infinite

• routers that sit behind each others max distance cant see each other…

• => limits maximum diameter of a RIP network

• if router Y got inforamtion about network N from router X

• -> it does not send infromation updates about that network to that router…

=> put into practice with poisoned reverse (set distatnce to the respective netowk to infinity (16)…)

• timers to regulate performance

• update timer

• invalid/timeout timer

• holddown timer

• flush timer

• marks rate in which RIP update messages are sent

  
  

• routers usually send updates every 30s

• -> thus, expect updates from neighbors every 30s

• => still need tolerance

• -> invalid timer starts when router receiives update

• -> if invalid timer times out

  • => the route from which the router expects an update will be set to unreachable (metric 16)

  • route still kept in routing table

  
  

• started after route is set to unreachable by update packet

• during holddown -> appropriate route marked as inaccesible

  • => routing information concerning better paths are suppressed

  • => advertised as unreachable

  
  

• after this interval of time has passed

• -> appropriate route will be deleted from routin table

• => starts right after having received last update

• set route to invalid -> distance 16

• RIP couldnt cope any longer with large and heterogeneous networks

• ptorocol is open -> specification is in public domain (RFC 1247)

• based on SPF algo (dijkstra)

• inter-AS routing protocol

• exchange routing information in between areas owned by IPSs but also within AS

• -> between eBGP (external BPG)

• -> inside iBGP (internal BGP)

• eBGP: network prefixes of AS propagated to gateway routers of other AS

• iBGP: gateway routers distributed prefixes they learned (through eBGP) in the AS (internal)

• information exchanged between BGP peers aside from network prefixes

• BGP routers exchange over semi-permanent TCP connection

• => patricipating routers (that share one of these semi-transparent TCP connections) are called BGP peers

• -> they exchange information

• AS_path

• Next-hop

• weight

• local preference

• multi-exit distriminator

• origin

• community

• when route advertisement passes through AS -> AS number added to ordered list oof AS numbers the route has traversed -> what AS to traverse to reach the destination of that prefix…

  
  

• connector between BGP and intra-AS routing

• -> the IP address of the router interface from which the AS path begins

• => thus, for BGP peers, next hop IP address of the connection between the peers

• for iBGP, eBGP next hop address carried into local AS

• not exchanged between routers

• -> cisco defined attribute local to router

• -> if router learns about more than one route to same destination

• -> route with highest weight will be preferred

• used to prefer an exit point from the local AS (-> as they usually have more than one exit point…)

• unlike weight, propagated through the AS

• -> route specific if there are more than one exit point

• MES / or metric attribute

• suggestion to external AS regarding preffered route into the AS that is advertising the metric

• indicates how BGP learned about a particular route

• one of three possible vlaues

• -> IGP, EGP or Incomplete

• provides way of grouping destinations

• -> so called communities

• -> to which routing decisions can be applied

• no-export, no-advertise, inter-net

1. if path specifies next hop that is inaccesible, drop the update

2. prefer path with largest weight

3. weights are same -> largest local preference

4. same -> prefer path that originated from BGP on this router

5. if no route was originated -> shortest AS path

6. if all same length -> prefer path with lowest origin type (IGP < EGP < incomplete)

7. origin codes the same -> lowest MED attribute

8. same MED -> external path over internal

9. still the same -> path through closest IGP neighbor

10. lowest IP address, as specified by the BGP router ID

• get shortest path

• detect routing lops => reject if AS of router already listed…

• link state advertisements (LSA)

• broadcasted

• within same hiararchical area

• RIP cannot operate in a hierarchical network topology

• OSPF can!

• -> newtork prefixes…

• largest: AS

• yes

• areas

• groups of contiguous networks and attached hosts…

• yes -> require respectively multiple network interfaces…

• => an area is interface specific…

• -> all interfaces connected to single area

• -> internal router IR

• area border router (ABR)

• autonomous system bondary router (ASBR)

• maintain seperate databaese for each area

• => each database contains LSA received from interfaces connected to respective area

• -> received from routers within that area

• yes -> share same information

• -> although it takes time to converge

• -> but mithg not if always close to convergence and then next change happens…

• entities (strictly) outside the area…

• gateway routers still in the area…

• OSPF gets along with less routing traffic tthatn it woudl fi the AS were not partitioned

• -> requires distribution of network entities (such as routers) to useful areas and points…

• yes -> intra-area routing when source and dest are in same ares

• inter area routing when src and dest in differetn areas

• respobsible for routing in between areas

• -> consists of all ABRs -

• -> backbone itself is OSPF area too

• - thus, applies same OSPF strategies to maintina information within backbone area

• scalability

  
  

• computation cost

• memory demand

• routing overhead

=> things like distance vector would never converge…

• each AS has unique , public autonomous system number (ASN)

• assigned by IANA

• prefix and

• ASN

• 16 bit

• 32 bit due to exhaustion of numbers

• private ASN -> used by ISP who apply BGP in private network…

• leased from regional internet registries (RIR)

• whois asxxxx command…

• multi path allow to send traffic over various paths which can lead to better throughput and reliability

• no -> small deviation from standard timer setting to avoid congestion problems… (as otherwise all would sent at the same time…)

• sends out hello messages to advertise its presence to the network

• starts sending hello messages periodically (as keepalive…)

• intra-AS -> focus on best path

• inter-AS -> take policy into consideration -> business policies…

• always take cheapest next hop (accumulative) until you reach destination…

• for each, have from list and initialize with infinity…

• node has entries to neighbors with cost

• shares cost to these destinations with neighbors

• incoming: enter the neighbors stuff in your from list

• update a couple of time if sth changes (best path) until nothing changes anymore…

• 1 byte type -> request (1) response (2)

• version -> of rip.. (e.g. v2)

• list of route table entries

  • IPv6 prefix

  • route tag

    • internal or external…

  • prefix length

  • metric

• destination

• nhid -> next hop id

• next hop ip (via)

• interface (dev)

• protocol used to get inforamtion (e.g. rip, kernel)

• metric for e.g. rip

• scope of destination -> e.g. scope link is direct unicast

  
  

• no -> onyl considers hop count…

• for important events -> propagate information quickly…

• bandwidht based…

• calculate for each link on a route and sum up over path…

• cost = reference_bandwidth / interface_bandwidth

  
  

• administrative distance

• -> e.g. 1 for static rotues

• -> OSPF 110 vs RIP 120, …

• 255 for unknown

• LSA database holding LSA for each area connected to

• router link states

• net link states

• link states

• intra area perfix link states

  
  

advantages:

• reduce network load (less flooding)

• smaller routing table and faster route calculations

disadvantages:

• increased design complexity (strategic positions, configuration…)

• areas might block paths… -> longer paths possible

• Hello -> discover OSPF neighbors , estbalish communication and send keepalives

• DB description -> LS database of sending entity -> sent to adjacent neighbors

• LS update -> ipdate for link-staes in its link state database

• LS acknowledge -> each LS packet must be acknowledged…

• LS request -> request info about (full or partial) link states of another router, has to be acknowledged either by LS update itself or LS acknowledge

• LSA type

• LS age -> age of lsa in seconds since origination -> initialize with 0 and update at each hop

• do not age -> not update L age…

• LS type

• ls id

• advertising router

• sequence numebr -> detection of duplicate and old lSA (larger more recent)

• checksum

• length

• BGP rather wait until they get all necesarry updates -> better convergence

• -> reduce overhead

• assume C knows from B that it can reach A with 2

• link between A and B cut

• B sets A to infinity

• next update -> B learns from C that it can reach A with metric 2 -> thus it can reach it with 3

• next update -> C learns from B, that the cost to A is now 3 -> updates accordingly and sets it to 4

• -> sends update to B, updates its own metric as it is based on Cs cost -> now 5

• ….

• => hapens due to routing loops