CCNA Routing Protocols 2013

Материал из eSyr's wiki.

Перейти к: навигация, поиск


[править] Introduction to routing protocols

Primary router responsibility:

  1. determining the best path
  2. forwarding packets

Router components:

  • CPU
  • RAM
  1. OS
  2. running config
  3. IP routing table
  4. ARP cache
  5. packet buffer
  • ROM
  1. bootstrap instructions
  2. diagnostic soft
  3. scaled-down OS
  • Flash memory (OS storage)
  • NVRAM (start-up config)

Bootup process:

  • Power-On Shelf Test (hardware testing)
  • Bootstrap loading (program to locate OS and load it to RAM)
  • OS loading
  • Config file loading (broadcast request if it doesn't exist)
  1. interface addresses
  2. routing info
  3. passwords
  4. etc

Interface - physical connector on router. Samples:

  1. LAN interface (RJ-45 UTP cable; ethernet encapsulation)
  2. WAN (serial; PPP, frame relay, high-level data link control)

Dynamic routing protocols perform:

  1. network discovery
  2. update and maintain routing tables

Routing table principles:

  1. Router makes decision alone.
  2. Different routers do not always have the same information in routing table.
  3. Info about the path doesn't provide info about return path.

Routes are added only after interfaces are configured. IP packet format:

  1. version
  2. IP header length
  3. destination & source address
  4. TTL
  5. protocol (upper-layer)
  6. etc

Ethernet frame fields:

  1. preamble
  2. source & destination address
  3. start-of-frame
  4. type/length
  5. etc

Hop-count - number of routers that packet must travel. Bandwidth - data capacity of link. Equal cost load balancing - using multiple interfaces with same metric to split data. Unequal cost load balancing is used in EIGRP. By default 4 equal paths are allowed. ICMP unreachable message is sent is there is no appropriate record in routing table and no default route. Network address is determined by adding IP address and subnet mask. Cables can be straight-through or crossover. Recursive lookup - multiple lookups in routing table before forwarding (e.g. to check connectivity and then determine next-hop). If interface is down, all static routes to it are removed. In static routing when exit interface is ethernet network, both exit interface and next-hop IP should be configured. Route summarizing is used for merging different networks.

[править] Cisco Discovery Protocol (CDP)

Getting information about directly connected devices. Operates on Layer 2. Info messages are periodically sent to neighbors:

  1. type of connected devices with interfaces
  2. interfaces to make the connections
  3. model numbers

Information provided about each neighbor:

  1. device id
  2. address list (for network layer)
  3. port identifier
  4. capabilities list
  5. platform

[править] Static routing

Cases for establishing static routing:

  1. Network consists of few routers.
  2. Network is connected to internet through single ISP.
  3. Hub-and-spoke topology (central hub).

[править] Dynamic routing protocols

Compare to static routing:

  1. independent of network size
  2. advanced knowledge required
  3. automatically adapts to topology
  4. suitable for all topologies
  5. less secure
  6. uses more resources
  7. route depends on current topology

Routing protocol purposes:

  1. remote network discovery
  2. maintaining up-to-date routing information
  3. choosing best path
  4. ability to find new best path is current is unavailable

Routing domain - collection of routers under a common administration. Interior gateway protocols are used within routing domain or individual networks. Exterior gateway protocols are under control of different organisations. Types of IGPs:

  1. Distance vector routing - routes are advertised as vectors of distance (e.g. hop-count metric) and direction (next-hop router or exit interface). Complete routing tables are sent to all neighbors periodically. Bellman-Ford or Ford-Fulkerson algorithm. Used when:
  2. simple networks
  3. not enough administrative knowledge
  4. specific networks (e.g. hub-and-spokes)
  5. worst-case convergence time are not a concern
  6. Link-state routing - creating complete view of the topology by gathering information from other routers. After network has converged updates are sent when there is topology change. Used when:
  7. hierarchical network design
  8. good administrative knowledge
  9. fast convergence is crucial

Classful routing protocols don't send subnet mask info. Examples: IGRP, RIPv1. Classless protocols include subnet mask in updates. Support discontiguous networks. Convergence - state when all routing tables are consistent. Metric is used to evaluate difference between available paths. Types:

  1. hop count - number of routers
  2. bandwidth
  3. load
  4. delay
  5. reliability - probability of failure
  6. cost - metric determined by OS or administrator

Administrative distance defines the preference of a routing source. The lower value is for more preferred route source. Cold start - situation when routers know nothing about the connected devices. Loopback interface - software-only interface that emulates physical interface. It is used by routing protocols, can be assigned an IP address. Null0 interface simulates exit interface. In is always up and discards traffic. Shouldn't be created or configured.

[править] Distance vector routing

Distance is number of hops to destination, direction represents exit interface. RIP:

  1. Hop-count metric (16 equal infinity).
  2. Updates are broadcasted every 30 seconds.


  1. Bandwidth, delay, load and reliability as composed metric.
  2. Broadcasting updates every 90 seconds by default.


  1. Unequal cost load balancing.
  2. Diffusing Update Algorithm to calculate the shortest path.
  3. No periodic updates.

Entire routing table is broadcasted to regularly. Routing protocol algorithm do the following:

  1. send and receive routing information
  2. calculate the best path
  3. detect and reach topology changes

Distance vector protocols features:

  1. simple implementation
  2. low resource requirements
  3. slow convergence
  4. limited scalability
  5. routing loops

Initial exchange - updates including only information about directly connected networks. Speed of achieving convergence consists of:

  1. speed of propagating a change to neighbors
  2. speed of calculating best path using collected information

EIGRP uses bounded updates:

  1. non-periodic
  2. partial updates are sent only when topology is changed
  3. only routers that need the information are updated

Routing loop - condition in which packet is continuously transmitting without reaching the destination. May be a result of:

  1. Incorrectly configured static routes.
  2. Incorrectly configured route redistribution.
  3. Routing tables were not updated due to slow convergence.
  4. Incorrectly installed discard routes.

Count to infinity problem - situation when updates increase metric to infinity that is no longer reachable. Solution - setting maximum value of hops. Split horizon rule - not advertising a network through the interface from which the update came. In other words, router send records that don't contain current exit interface in routing table. Route poisoning is used to mark the route as unreachable and send updates to other routers. Split horizon with poison reverse - principle to ensure that router with unreachable network is not susceptible to incorrect updates about that network. Time to live (TTL) - 8-bit counter in IP header that limits number of hops the packet can traverse.

[править] RIP version 1


  1. distance vector protocol
  2. the only metric is hop count
  3. routes with hop count greater than 15 are unreachable
  4. broadcasting every 30 seconds
  5. classful
  6. no VLSM & CIDR support
  7. administrative distance 120
  8. by default updates are sent to all RIP-configured interfaces (even if there is no RIP-device) (can be solved using passive interface)
  9. can have two exit interfaces with the same network address even if networks are discontiguous
  10. if no version type is specified, receives v1 and v2 updates


  1. invalid (setting metric to 16 if update from current route hasn't been received for 180 seconds)
  2. flush (removing route after 240 seconds silence)
  3. holddown (unreachable route stays in this position for 180 seconds to let routers learn about the failure)

Holddown timer usage:

  • Router receives triggered update indicating that some network changed is no longer accessible.
  • Router marks the network as possibly down and starts the holddown timer.
  • If update with better metric is received, holddown timer is removed.
  • Other updates are discarded.
  • Packets are still forwarded.

Triggered updates (immediately sent):

  1. Interface changes state.
  2. Changing state to/from unreachable.
  3. Route is installed in routing table.

Message format:

  • data link frame header (MACs)
  • IP header packet (IPs, protocol field-17 for UDP)
  • UDP segment header (src/dst port = 520)
  • RIP message
  1. command (request/responce)
  2. version
  3. address family id (2 for IP, 0 for requesting full table)
  4. IP routes (25 maximum) + metric

Information exchange:

  • Each RIP-configured interface sends request for full routing table.
  • RIP-enabled neighbors send response.
  • Routes are added or updated if needed.
  • After updating triggered updates are sent to RIP-enabled interfaces. When there is a packet collision (in hubs), RIP _JITTER contains randomly chosen time to wait before next update.

Boundary router has interfaces in more than one classful network. Update rules:

  1. If the update and the received interface belong to the same major network, the subnet mask of the interface is applied to tie network in routing table.
  2. If networks differ, the classful mask of the network is applied.

[править] VLSM and CIDR

Not supported by RIPv1 and IGRP. Designed for more effective use of IP addresses. Network classes:

  1. A (1-126 in first octet; subnet mask
  2. B (128-191;
  3. C (192-223;

Significant bits refer to network, insignificant to host. Variable length subnet mask (VLSM) can be thought as sub-subnetting.

  1. Conserves address space.
  2. Ability to specify a different subnet mask for the same network number and different subnets.

E.g. can be divided in 256 networks 10.x.0.0/16. Classless inter-domain routing (CIDR) - form of route summarizing.

  1. Reduces the number of entries in routing updates and routing tables.
  2. Reduces bandwidth utilization.

Algorithm (calculating a route summary):

  • List networks in binary format.
  • Count the number of left-most matching bits.
  • Copy the matching bit and add the rest zero bits.

Supernet - group of major network addresses summarized as single network.

[править] RIP version 2


  1. classless
  2. next-hop addresses are included in updates
  3. multicasting instead of broadcasting (takes up less bandwidth and less processing of non-RIP devices)
  4. authentication option available (accepting packets from devices with the same password)
  5. holddown and other timers, triggered updates, split horizon, poisoning
  6. auto-summarizing by default as in RIPv1 (can be disabled)

RIPv2 message format:

  1. command (request/responce)
  2. version
  3. address family id (2 for IP, 0 for requesting full table)
  4. route tag
  5. subnet mask
  6. next hop address (used to identify a better hext-hop address than router address) ( refers to the best next-hop address)
  7. IP routes (25 maximum) + metric

[править] The routing table

Source network types:

  1. directly connected
  2. static routes
  3. dynamic protocols

Level 1 route is a route with subnet mask equal or less than the classful mask of network address. Such routes can function as:

  1. default route - static route with the address
  2. supernet route (mask less than classful)
  3. network route (mask is equal to classful)

Ultimate route includes:

  1. either a next-hop IP address
  2. and/or an exit interface

Parent route doesn't contain any next-hop IP address or exit interface. It is automatically created when a route with a greater mask than the classful mask is entered into the routing table. Level 2 route - route that is a subnet of a classful network address. Parent route can be subnetted or variably subnetted (VLSM). Routing behaviour (not the same as protocols) (affects lookup process only):

  1. classful
  2. classless

Route lookup process:

  • Examining 1 level routes.
    • If the best match is ultimate route then forward.
    • Otherwise (parent route) continue.
  • Examining child routes.
    • If there is a match then forward.
    • Otherwise continue.
  • If classful behavior then drop. If classless behavior then continue searching supernets , including the default route, with less match.
  • Forward if there is a match.
  • Drop.

[править] EIGRP


  1. distance vector
  2. authentication allowed
  3. auto-summarizing by default

Message format:

  • Data link frame header
  • IP packet header
  • EIGRP packet header
  • Type/length/values (TLV) types

EIGRP packet header fields:

  1. opcode
  2. update
  3. query
  4. reply
  5. hello
  6. autonomous system (AS) number - number to track multiple EIGRP instances


  1. parameters
  2. weights for composite metric (only bandwidth and delay by default, equally weighted)
  3. hold timer (time for neighbors to wait before considering the advertising router down)
  4. IP internal (used for advertising routes within an AS)
  5. delay (sum of delays from src to dst in units of 10 microseconds)
  6. bandwidth (lowest configured bandwidth of any interface along the route)
  7. subnet mask (prefix length)
  8. destination address (24bits + additional 32bits if needed)
  9. IP external (used for importing external routes into routing process)

EIGRP is capable of several different routing protocols IP, IPX, AppleTalk using protocol-dependent modules (PDM). Reliable Transport Protocol (RTP) - protocol for exchanging information packets. Can send packets either multicast or unicast. Packet types:

  1. hello (discover neighbors and form adjacency) (multicast unreliable delivery)
  2. update (propagate routing information is sent only when necessary and to routers that need it) (multicast or unicast dependent on quantity)
  3. acknowledgement (when reliable delivery is used; contain a nonzero ack number) (always unicast)
  4. query and reply (used by DUAL; always reliable delivery) (queries are multicast, responses are unicast)

Hello's are sent every 5 seconds (60 on slow connections). Holdtime is three times the hello interval. DUAL finite state machine (FSM) track all routes, uses efficient loop-free least cost path. Wildcard mask - inverse subnet mask. Null0 is included as a child route if:

  1. There is at least one EIGPR-learned subnet.
  2. Auto-summarizing is enabled.

Null0 is always selected if there is no match regardless the classless behavior. Metric consists of:

  1. bandwidth (link characteristic)
  2. delay (set by administrator)
  3. reliability (probability of fail)
  4. load (amount of traffic utilizing a link)

\text{EIGRP metric} = \left(\frac{10.000.000}{\text{bandwidth kbps}} +
\frac{\text{sum of delays}}{10}\right)*256

Diffusing update algorithm (DUAL) (uses topology table and neighbor table to build the routing table):

  1. Successor - neighboring router that is used for packet forwarding and is the least-cost to the destination network).
  2. Feasible distance (FD) - the lowest calculated metric to reach the destination.
  3. Feasible successor (FS) - neighbor who has a loop-free backup path to the same network as successor by satisfying the FC.
  4. Reported distance (RD) - total metric along a path to destination (neighbor's FD).
  5. Feasibility condition (FC) is met when a neighbor's RD is less than the local router FD.

Topology table holds information about the successor, FD and any FS with their RD. Passive state means that DUAL is not performing computations.

[править] Link-state protocols

Dijkstra's algorithm (shortest path first). Routing process:

  • learning about directly connected networks (detecting that interface is up)
  • saying hello to neighbors on directly connected networks
  • building link-state packet (LSP) containing the state of directly connected links
  • flooding LSP to all neighbors, who then store it in database
  • using database to construct a complete map of the topology and compute the best path to each destination network

LSP includes:

  1. interface IP and subnet mask
  2. type of network (ethernet, point-to-point)
  3. link cost
  4. any neighbor routers on that link
  5. sequence number and aging info (help to manage flooding and to keep the database up-to-time)

Unlike distance vector protocols, SPF is calculated after the flooding is complete. LSPs are sent when:

  1. initial startup
  2. topology change

Overall advantages:

  1. building a topological map
  2. fast convergence
  3. event-driven updates
  4. hierarchical design (concept of areas)

IS-IS is mainly used by ISPs and carriers.

[править] OSPF


  1. link-state routing protocol
  2. AD 110
  3. authentication is allowed

Message format:

  • Data link frame header
  • IP packet header
  • OSPF packet header
  • OSPF packet type-specific data

Packet types:

  1. hello
  2. database description (DBD) (check for database synchronization between routers)
  3. link state request (LSR) (request for specific database records)
  4. link state update (LSU) (reply to LSR)
  5. link state acknowledgment (LSAck) (confirm receipt of the LSU)

Usage of hello packets:

  1. discover neighbors and establish adjacencies
  2. advertise parameters on which routers must agree to become neighbors
  3. elect designated router (DR) and backup DR (BDR) on multiaccess networks

OSPF packet fields:

  1. type (hello, DD, LSR, LSU, LSAck)
  2. router ID
  3. area ID
  4. network mask (associated with sending interface)
  5. hello interval
  6. router priority
  7. DR ID if any
  8. BDR ID if any
  9. list of neighbors (IDs)

Hello interval - time before hellos (10s on multiaccess and point-to-point, 30 on non-broadcast multiaccess segments e.g. frame relay). Dead interval - time to wait until neighbor is considered down if there is no hellos. 4 times the hello interval. To establish connection network type, dead and hello intervals must be the same. DR is responsible for updating all other routers when a change occurs in the multiaccess network. LSA contains route information for destination networks. Each router has link-state database containing LSAs from neighbors. OSPF area - group of routers that share link-state info. Multiarea is used for isolating unstable networks and for storing smaller databases. How to choose router ID:

  • configured IP address
  • if not, choose highest IP of any loopbacks
  • if not, highest active IP of any physical interface

Router ID is chosen with first 'network' command and changes only if ospf process is killed. Flapping link - network that cycles between up and down. SPF shedule delay - 5 seconds delay after receiving an LSU before running SPF. Used to minimize flapping link problem. Hold time - 10 seconds delay between rerunning SPF. Retransmit interval is time before repeated advertisement is sent if there was no ack).

\text{OSPF Cisco metric} = \frac{10^8}{\text{bps}}

The cost of OSPF route is accumulated value from one router to the destination. Multiaccess network - network with more than 2 devices on the same shared media (e.g. ethernet LAN). OSPF network types:

  1. point-to-point
  2. broadcast multiaccess
  3. nonbroadcast multiaccess (NBMA)
  4. point-to-multipoint
  5. virtual links

Challenges in multiaccess networks:

  1. creation of multiple adjacencies: \text{Total adjacencies} = \frac{n(n-1)}{2}
  2. extensive flooding of LSAs (the problem is to introduce each device to other devices)

DR and BDR are chosen to solve flooding problem (only in multiaccess).

  • DR is a router with highest interface priority.
  • BDR is a router second highest interface priority.
  • If priorities are equal ther compare by router IDs.
  • Other router are marked as DROther.

Neighbor states:

  1. full
  2. 2way (two drothers form adjacency)

DR remains DR until:

  1. DR fails
  2. OSPF process on it fails
  3. multiaccess interface on it fails

Routers with priority 0 will never be DR or BDR. Autonomous system boundary router (ASBR) is located between OSPF routing domain and non-OSPF network. OSPF area types:

  1. Backbone area forms the kernel. It should distribute routing information between non-backbone areas.
  2. Standard area is created by default. It receives link updates, summary routes and external routes.
  3. Stub area don't receive information about external routes but receives it from other areas.
  4. Totally stubbed area don'r receive information from other areas. Cannot contain ASBR.

LSA types:

  • router link state update
  • network link state
  • summary network LSA
  • ASBR summary
  • AS external
  • + some other ...
Личные инструменты