Wednesday, April 29, 2015

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 costper 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.

Friday, April 3, 2015

IPv6. Introduction to ICMPv6.

Wee already have some information about IPV6 packet structure and IPv6 addressing.
This post will be about ICMPv6 protocol. It is gonna be upper layer protocol for IPv6 packet and "next header" value of the main ipv6 protocol will be set to 58.

Header ICMPv6

After host/router decode this value it knows that the next header will be ICMPv6 header:
ICMPv6 protocol message have the next format:


Pic.1 ICMPv6 message.


Type

The "type" field value is determines which data encoded to ICMPv6 message ( ping request, ND protocol message e.t.c)
All ICMPv6 messages are divided into two common types : error messages and informational messages. Informational messages and error messages are different in it's "type" field: error messages have "type" value <128, all other values to 255 are informational.
Informational messages are: ICMPv6 request/response messages(type 128/129) , Neighbour Discovery Protocol messages (will be described in future post) .
Error messages are: Destination unreachable message (Type=1) , Packet too big (Type=2), Time Exceeded (Type=3), Parameter problem (Type=4)

Code

The "code" field depends on the type of the message. Different codes of messages of the same type have different functions.

Checksum

"Checksum" field is used to detect some data corruption in the ICMPv6 message. As you already know there is no any header shecksum inside IPv6 packet but "Checksum" field protects ICMPv6 message of any errors. 


Message body

Message body is a payload of ICMPv6 protocol message. for example there is a ICMPv6 request message sent from source to destination IPv6 addresses. You can see "Identifier", "Sequence" and "Data" field that are message body of the ICMPv6 Echo request message.



Pic.2 ICMPv6 Echo request message.



Read RFC4333 to dig deeper ad to find full information about other ICMPv6 messages values.