Computer networks -- 2007-2008 -- info.uvt.ro/Course 7

Important! These pages are somehow outdated and it is recommended to consult the newer version at Computer networks -- 2008-2009 -- info.uvt.ro (by Ciprian Crăciun).

Quick links:


IP packet

edit
  • packet structure:
    • version -- 4 bits;
    • header length -- 4 bits:
      • expressed in number of 32 bit words;
    • priority and type of service -- 8 bits:
      • priority -- 3 bits;
    • total length -- 16 bits:
      • expressed in bytes;
      • including header and data;
    • identifier -- 16 bits:
      • unique IP packet identifier;
    • flags -- 3 bits:
      • tells if fragmentation has occurred;
    • fragment offset -- 13 bits:
      • used for packet reassembly;
    • time to live -- 8 bits;
    • protocol -- 8 bits:
      • 1 for ICMP;
      • 6 for TCP;
      • 17 for UDP;
    • header checksum -- 16 bits:
      • CRC for the header only;
    • source IP address -- 32 bits;
    • destination IP address -- 32 bits;
    • options -- 0 or 32 bits;
    • data;
  • links:

IP control protocols

edit
  • ARP -- Address Resolution Protocol;
  • used to find the hardware address of a host's known network address;
  • usable only inside the local network;
  • it involves also an ARP cache;
  • it works by sending a broadcast asking the node that has that specific IP address to reply;
  • ARP is for the network layer as DNS is for the application layer;
  • links:

RARP

edit
  • RARP -- Reverse Address Resolution Protocol;
  • it works just like ARP but it inverses the query parameters;
  • it could be used by a disk-less machine to find out its IP address based on its MAC;
  • links:

ICMP

edit
  • it is a management protocol;
  • it allows the router to inform hosts or other routers of various events:
    • destination unreachable;
    • hops -- used to indicate that the TTL of a message has reached 0, and the packet hasn't found the destination;
    • ping;
  • links:

IP routing

edit
  • routing: the process of moving packets from one network to another;
  • router:
    • networking device that implements routing;
    • it sits at the border of two layer 3 networks;
    • it can be an ordinary computer or a dedicated hardware router;
  • routing vs routed protocol:
    • routing protocol:
      • used by routers to dynamically determine the routes;
      • they are invisible to the normal user;
    • routed protocol: they are responsible for transferring user data once the path has been determined;
  • routing:
    • (see first line);
    • it is based on logical -- layer 3 -- addresses, in our case IP addresses;
    • routing doesn't take into account the exact destination -- host -- address, but only the network part;
  • local vs remote network;
  • to be able to route a packet we need to know:
    • destination address;
    • possible routes to all the remote networks;
    • (and it can deduce) the best route to each remote network;
    • (maybe) neighboring routers;
  • routing table;
  • routing types:
    • static routing;
    • dynamic routing;
  • default route;
  • asimetric routes;

Simple routing algorithm

edit
  • case study:
    • two hosts:
      • 172.16.10.2 -- host A;
      • 172.16.20.2 -- host B;
      • 172.16.10.1 and 17.16.10.2 -- a router connecting the two networks;
  • host A generates a packet (for example an ICMP echo -- ping -- packet) that it wants to send to the host B; the packet also contains the source and destination address;
  • host A determines if the destination is on a local or a remote network; in our case it is on a remote address;
  • host A will send the packet to the default router;
    • for this the ARP protocol (or the ARP cache) is used to determine the MAC of the router;
    • the IP packet is sent to the data link layer together with the MAC address;
    • the router receives the packet from the data link layer and hands it to the network layer;
  • the router checks the routing table to see where the packet should be sent next;
    • in our case the router sends the packet to the host B -- again the whole ARP, data link scenario occures;
    • host B receives the packet;
  • host B hands the packet to the ICMP protocol module;
  • host B generates a reply and the whole scenario happens again;

Static routing

edit
  • the routing table is managed by an administrator that fills all the possible routes and their metrics;
  • advantages:
    • low CPU and memory overhead;
    • no bandwidth usage;
    • greater security;
  • disadvantages:
    • the network topology must be thoroughly known by the administrator;
    • the update process is painful;
    • not usable in larger networks;
    • it doesn't scale with the number of networks;
  • class-ful vs class-less routing:
    • sending or not subnetting or VLSM information;

Dynamic routing

edit
  • the router uses a protocol to exchange information with direct neighboring routers, in order to build the routing table;
  • advantages:
    • no human intervention is needed;
    • the topology is not needed to be known in advance;
    • the network is optimized based on the actual situation;
    • it scales well with the number of networks;
  • disadvantages:
    • higher CPU and memory usage;
    • bandwidth consumption;
    • big convergence times;
  • AS -- Autonomous System:
    • a collection of networks under the same administrative domain;
  • types:
    • IGP -- interior gateway protocols:
      • used inside an AS;
      • all the routers share the same routing tables;
      • RIP -- Routing Information Protocol;
      • IGRP -- Interion Gateway Routing Protocol;
      • EIGRP -- Enhanced Interior Gateway Routing Protocol;
      • OSPF -- Open Shortest Path First;
    • EGP -- exterior gateway protocols:
      • used outside an AS, so between different AS;
      • BGP -- Border Gateway Protocol;
  • administrative distances:
    • a number between 0 and 255;
    • 255 it means it will never be used;
    • it should represent the thrustworthiness of that link;
    • usually a route with the lowest distance is the one used;
    • examples:
      • connected -- 0;
      • static route -- 1;
      • EIGRP -- 90;
      • IGRP -- 100;
      • OSPF -- 110;
      • RIP -- 120;
      • unknown -- 255;
  • metric:
    • a value between 0 and 255;
    • it should denote the efficiency of the link (bandwidth, delay, etc.);
  • routing protocol types:
    • distance vector protocols: RIP, IGRP;
    • link state protocols: OSPF;
    • hybrid: EIGRP;

Distance vector routing protocols

edit
  • these protocols find the best route based on the estimated distance;
  • a good example would be the number of hops;
  • general working principle: each router sends to its neighbors its entire routing table;
  • also called routing by rumor;
  • if all the routes to a network have the same metric, then load balancing is done on these routes;
  • because of slow network convergence time routing loops could occure; as a solution:
    • any network with a number of hops greater than -- 15 in the case of RIP -- will be deemed unreachable;
    • or split horizon could be used -- each router will keep track of where a route was learned from and will not advertise that way;
    • route poisoning -- when a link goes down it's hop count is set to 16 and advertised, thus it is marked as unreachable;
  • other problems that could occure are when a link keeps changing its state rapidly;

RIP -- Routing Information Protocol

edit
  • it is a distance vector protocol;
  • it is an open standard;
  • it sends its table about every 30 seconds;
  • it uses hop count as distance;
  • it has a maximum hop count of 15;
  • any network with over 16 (including) hops is deemed unreachable;
  • it is suitable for small networks, but not for larger ones;
  • versions:
    • v1 -- class-ful routing;
    • v2 -- class-less routing;
  • timers:
    • route update timer -- when it should send its routing table -- about 30 seconds;
    • route invalid timer -- when how much it will keep a route without receiving an update about it, and when it elapses it tells to the neighboring routers -- about 180 seconds;
    • route flush timer -- how much an invalid route should be still kept -- about 240 seconds;
  • as a disadvantage: too expensive because of the bandwidth used and the convergence time;

IGRP -- Interior Gateway Routing Protocol

edit
  • a Cisco proprietary protocol;
  • maximum hop count of 255, but with a default of 100;
  • it uses a composite metric: bandwidth, delay, (maybe MTU);
  • in general it works like RIP;
  • it works in larger networks;
edit
  • also called shortest path protocols:
  • each router keeps three tables:
    • directly connected routers;
    • entire network topology;
    • the actual routing table;
  • general working principle: each router sends to all the other routers the state of its links;
  • the advantage of these protocols is that they can determine the actual network topology;

OSPF -- Open Shortest Path First

edit
  • it is an open standard;
  • it uses Dijkstra's algorithm for minimum spanning tree;
  • it sports VLSM;
  • it uses bandwidth as a metric;
  • it has fast convergence times;
  • it allows hierarchical networks:
    • by splitting the network is areas;
  • a router keeps a tree for each area it is in;
  • the tree contains the best path to that given network;
  • the best path is elected based on the metric (bandwidth);