Routing protocols. Fundamentals.

Routing protocols. Common. 

Routing protocol is a language a router speaks with other routers to share reachability and status of networks.

Dynamic routing can sense topology changing, share this info and compensate it.

Routing protocols are built around an algorithm - step-by-step procedure to solve the problem:

-pass info

- receive info

- count optimal paths and built routing table

- process topology changing

Metric.

Metric - is a variable assigned to routes to rank them as most or least preferred.

Different routing protocols use different metrics:

- Hop count. (RIP) -Load (such metric can cause route flapping)

- Bandwidth. (EIGRP) - Delay (time, packet traverse a route)

- Reliability (is changed by admin or by packet drops)

- Cost (can be defined by any policy; can be set by admin; is a generic term when speaking of route choice).

Lowest cost path = shortest path = better path.

 Convergence.

Convergence - is a bringing all route tables to a state of consistency.

Convergence time - time need for protocol to calculate the best path

Routing loop.

Routing loop -continuous circling traffic between two or more hops.

 Load balancing.

Load balancing - forwarding packets to the same destination by different paths.

Load balancing can be equal cost and unequal cost, per packet and per destination.

Distance vector routing protocols.

Distance vector routing protocols (algorithm - Belman-Ford, routing by rumor, RIP, EIGRP, IGRP)

Routes are advertised as vectors(distance,direction),where distance=metric, direction=next-hop router. Counting best path is distributed task.

Neighbors.

Neighbors - when routers share direct link or logical link(BGP). Distance vector protocols sends updates to neighbors. Each router must share it's updates to all neighbors (hop-by-hop updates) until routing info becomes consistent.

Updates.

Periodic updates - updates transmitted in a certain period. frequently - slow convergence, fast updates - CPU overloading

Broadcast updates - after starting the router. Updates sends to 255.255.255.255;

Full routing table updates - the router under distance vector protocol sends whole routing table to neighboring routers.

Asynchronous updates - are used in broadcast networks to prevent collisions due broadcasting updates ( by adding randomness to update period).

Triggered updates - if a metric changes for route, it immediately sends update, doesn't wait for update timer, but regular updates still occurs and router can receive bad information from a non-converged router with regular updates and erase correct information received from triggered updates.

Distance vector convergence.

Route invalidation timer/timeout for each routing entry to prevent black holes when some network goes down. Timeout is near 3 - 6 updates periods.

Reverse route and split horizon - split horizon is preventing reverse route and routing loops caused by flapping of reverse route. Split horizon can be simple and with poisoned reverse(advertise reverse routes with infinite metric).

Counting to infinity - when routes flap it can cause loop between three or more routers(imagine ring topology) and increase metric from one to another until metric becomes infinite. Split horizon doesn’t help, route just make a circle. Maximum network diameter is 15 hops.

Holddown timers - timer sets after route metric changes, until this timer expires, none of new updates will be accepted. Changing this timer will cause convergence time changing.

Link state routing protocols.

Link state routing protocols (Dijkstra algorithm and SPF ; OSPF, ISIS).

Each router generate information about itself, directly connected links (state of this links) and directly connected neighbors. Each

1. Each router establish neighbor relationships - adjacency with each of neighboring routers
2. Each router sends LSAs to it’s neighbors (flooding LSAs)
3. Every router floods LSAs stored in it’s database.
4. When all copies of all LSAs are stored in router’s database, router start SPF algorithm to count the best path.

LSA (Link state advertisements) - contains a list of router’s links with info about this link: state, metric cost, neighbors on that link .

Neighbor and Router ID (RID) - neighbor discovery procedure between routers using hello protocol, exchanging packets; RID is used to uniquely determine every router;

Hello protocol(HP) - during HP neighbors exchange hello intervals,dead timers,different flags and timers to maintain adjacency.

Link state protocol adjacency, convergence and flooding mechanism.

Adjacency - routers are fully adjacent when their databases are synchronized; adjacency is controlled by hello protocol packets used as keepalives.

Link state flooding - in link sate protocols LSAs are forwarded immediately as it’s received or updated, whereas distance vector protocols must first run its algorithm (Belman-Ford) then update route table before updates sent. LS converge faster then DV after the topology changes. Flooding is a complex process and should be efficient and without any mistakes.

Sequence Numbers - used to notify routers that database is synchronized, newest LSAs are in database. Sequencing is used to maintain actual database and not to react and no to believe wrong info in non-actual (delayed or corrupted) LSAs. There are some procedure to make flooding more reliable and easy: LSA aging, LSA sequencing, creating areas.

Sequence number(SN) space - there are some types: linear, circled, lollipop shaped sequence number spaces. It depends on SN_space how router reacting on SN closing to the maximum. Most popular questions and rules:

- Q:how router knows it’s last generated LSA’s sequence number

- A: Router R1 which sees that neighbor R2 is alive after restart, matches R2’s LSA in it’s own database and sends it to R2. R2 generating LSA with actual SN

-Q: What router does when it’s link state process is run out of sequence number because of some internal error? (Note that router was not restarted nor lost adjacency)

-A: In this situation router must wait until all it’s LSAs will be aged out

Sequence number rule: The “Jump” the router might take in sequence numbers must be limited.

Today sequence number space is fully linear. After SN reaches the maximum - routing process must flush LSAs from LSDB before restarting.

Aging - special field inside LSA’s packet incremented due flooding process by each router. Protocol define MaxAgeDiff value to match some corrupted LSAs and MaxAge value to match LSA which should be flooded to all routers and flushed from LSDB.

If LSA haven’t flushed from all databases there is mechanism that renew LSAs due some period - LSRefreshTime

Topology database, areas and autonomous systems.

Link State Database (LSDB or topological database) - each router under routing protocol process maintain topological database (stores all actual LSAs)

Information related to LSA is:

1. Age and sequence number - to manage flooding process

2. Router ID, connected networks, neighbors and link costs - to build shortest path determination.

Areas - link state protocol can not maintain network which contains thousands of routers because of big database of LSA and SPF computation. Area confine flooding and you need maintain database only for routers within that area.

ABR (Area Border Routers ) - routers connecting two areas, belong to both. To send packet to another area router should know how to reach ABR.

Autonomous System (routing domain aka “AS”)- larger areas, a group of routers under one administrative domain (can be different routing protocols).

IGP (Interior Gateway Protocol) - routing protocols run within an AS.

EGP (Exterior Gateway Protocol) - routing protocol between autonomous systems.