CS-09 – Data Communications and Networks

AGENDA (Session 11)

Network Layer, VC, Datagrams

Routing Algorithms

(Shortest path, Flooding, Flow Based, Distance Vector, Link State, Hierarchical, Mobile Host, Broadcast, Multicast)

Congestion Control

(Leaky Bucket, Token Bucket)

IP Protocol

IP Classes

Internet Control Protocols

(ICMP, ARP, RARP, BOOTP)

OSPF

Network Layer

· Lowest Layer of end to end transmission.

· Communication subnet – set of routers.

· Shall work Independent of Topology.

· Shield Transport Layer.

· Uniform Network Addresses.

· Unreliable Connectionless, Reliable Connection-Oriented models are popular.

Virtual Circuits:

· Mostly Connection Oriented.

· Same Route for every packet.

· Router Remembers every message packet direction.

· Virtual Circuit Number on router is of local significance.

· Charging on usage time and amount of information transferred.

Datagram:

· Mostly Connection-Less.

· Each packet can be routed independently, so it shall contain full destination address.

· At router, maintain a table of all possible destination routers.

Tradeoffs between VCs and Datagram:

· Memory space inside router vs. High bandwidth usage due to longer address.

· Setup Time vs. address parsing time.

· Easy vs. difficult congestion control.

· Router crashing problem vs. other routes for packets.

IN PRATICE CONNECTIONLESS SERVICE CAN RUN OVER VIRTUAL CIRCUITS LIKE IP OVER ATM SUBNET.

Routing Algorithms

· Related to VC or Datagram nature of traffic.

· Correctness, Simplicity, robustness, stability, Fairness and optimality desired.

· Non-adaptive of static routing – Prefixed Route.

· Adaptive (Adapts to changing traffic or topology).

· Sink Tree (Optimal path (less no. of hops) from source to destination – rooted at destination).

· Router algorithm tries to discover sink tree.

Shortest path Routing:

· Route Distance and best known path is filled at each routing node.

· At each node all further connections are also examined and filled.

Flooding:

· Rcvd packet sent on all directions other then sender.

· Hop Count added in packet, that is decreased from maximum path length to zero.

· Selective Flooding is done to send packet in direction towards receiver only.

· Robust and shorter delay but overhead of flooding could be high.

Flow based Routing:

· Considers Line capacities between nodes.

Routing Algorithms – Contd.

Distance Vector Routing:

· Dynamic tables for distance of neighbors and line to use.

· Entry for all stations is made at each router.

· Was frequently used on NET before Link State Routing.

· Metric could be hops, queue length, Time-Delay (Seen by Echo Packets).

· Count to infinity problem exists – when node goes down to up is detected early, but from up to down it is detected late.

Link State Routing:

· Discover and measures delay/cost to each neighbor.

· Tell this to all neighbor and compute shortest path to all routers.

· Delay is measured by echo packets to all routers.

Hierarchical routing:

· For large routing network hierarchical table keeping is essential.

· Router keeps table entry for all regional routers + direction entries to all other regions.

· Path may only be optimal within a region.

Mobile Host Routing:

· Home agent gives address of foreign agent where mobile host is located.

· Home agent tunnels first packet to foreign agent subsequent packets are directly tunneled to foreign agent.

Broadcast and Multicast Routing

Broadcast Routing:

· Packet to each destination separately (wastes bandwidth) – Not a right approach.

· Flooding (Shall generate too much traffic) – not right.

· Multi-destination Routing (Packet + List of destination) – Right approach.

· Spanning Tree – Loop free tree (Copy packet to all spanning tree lines).

· Reverse Path Forwarding (copy packet on forward lines, if it is the same line on which it arrived as a shortest path source).

o Reasonably easy and efficient and easy

o Doesn’t require to router to know spanning tree.

Multicast Routing:

· Messaging to a group.

· Group management required.

· Router Knows group no. of the host.

· First whole spanning tree is formed, then group based spanning tree is formed.

· Core based tree is alternate approach, where spanning tree is fixed from core and sender first sends packets to core, who then multicasts.

Congestion Control

· Many packets that arrive on input of a router start needing same output line.

· Adding more memory might produce more re-transmission due to frequent timeout and thus increases congestion.

· Can be due to slow processors and less bandwidth.

· Congestion is between multiple hosts in a subnet, while flow control is point-to-point (For matching fast sender to slow receiver).

· Algorithms applied are open loop ( Source action, destination action) or closed loop ( Explicit Feedback, Implicit feedback).

· To improve situation either load is decreased to resources are increased (Using spare routers, Multiple Router splitting)

· Congestion alog. Are best applied to VCs then Datagrams (Applied in Transport Layer)

· Traffic shaping : Regulate average rate, preagreement of traffic pattern).

Congestion Control Algorithms

Leaky Bucket:

· Inflow at any rate but outflow at constant rate.

· Discard anything entering full queue state.

· Put fixed number of bytes out/clock tick.

· E.g. 25 MB/sec burst for 40 msec=1MB Data ( c ) leaks at 2 MB/sec (r) upto 500 msec.

Token Bucket:

· Outflow permitted by destroying token that are earlier acquired at a fixed clock rate.

· Burst upto bucket size are allowed first and after that it is regulated at outflow rate.

· Variation of algorithm can be designed for no. of bytes instead of packets. Fractional tokens left in this process are reserved for next cycle.

· S=C/(M-r) (here S= Burst time, Maximum Output rate, C= can size, r= Token arrival rate

SMOOTH TRAFFIC IS OBTAINED BY PUTTING A LEAKY BUCKET ARRANGEMENT ON FRONT OF A TOKEN BUCKET ARRANGEMENT.

IP (Internet Protocol)

THE IP FRAME:

· Header + Text Part.

· Header : 20 byte fixed + variable (0-40) bytes optional.

· Version – 4 bit.

· Header Length – 4 bit.

· Type of Service – 8 bit (Precedence – 3 bit, Delay, throughput, reliability – 1bit each, 2bit spare).

· Total Length – 16 bit (Header + Data).

· Identification – 16 bit (All fragments have same ID)

· Unused – 1 bit

· Don’t Fragment – 1 bit

· More Fragment – 1 bit (All but last fragment has this bit set)

· Fragment offset – 13 bit (Maxm. 8192 fragment/datagram)

· Time to live – 8 bit (Counts hops, dies with 0)

· Protocol – 8 bit ( Handover to which port of Transport)

· Header Checksum – 16 bit (Recomputed at each hop)

· Source Address – 32 bit (Class, Network ID, Host)

· Destination Address – 32 bit (Class, Network ID, Host)

· Optional (Security, complete routing path, necessary points in path, route history, timestamp).

IP ADDRESSING:

Class A – MSB 0, NW-7 bit, 1.0.0.0 to 127.255.255.255

Class B – MSB 10, NW-14 bit, 128.0.0.0 to 191.255.255.255

Class C- MSB 110, NW-21 bit, 192.0.0.0 to 223.255.255.255

Class D – MSB 1110, Multicast, 224.0.0.0 to 239.255.255.255

Class E – MSB 11110, Future address, 240.0.0. to 247.255.255.255

Special IP ADDRESSES:

All 0 bits= this host, NW bits 0= host on this network, All 1 bits=broadcast on local network, All host bits 1 broadcast on distant network, 127.x.x.x. for loopback

Internet Control Protocols

ICMP (Internet Control Message Protocol):

· Monitors IP network for Errors.

· Destination Unreachable, Time Exceeded, Parameter problem, Source Quench, Redirect, Echo Request, Echo reply, Time stamp request, Time stamp reply.

ARP (Address Resolution Protocol):

· Resolving IP address to actual Ethernet address (48bit).

· Sender broadcasts “Who owns a given IP”. Everyone checks its own and returns the matching address.

· IP packet is sent as payload on Ethernet.

· Made efficient by giving Ethernet address along with its broadcast, cache previously received address, broadcast at bootime.

· ARP cache shall timeout to allow changes.

RARP (Reverse Address Resolution Protocol):

· Given the Ethernet address and finds IP.

· Newly booted machine send its Ethernet address and asks everyone of its IP.

· RARP server replies.

BOOTP:

· RARP doesn’t go across router, but BOOTP uses UDP messages to travel across router.

Interior Gateway Routing

· Routing with Many Autonoums Systems

· Distance Vector-Link State-OSPF

OSPF (Open Shortest Path First):

· Open Standard for everyone to adopt it.

· Variety of metrics: Physical distance, delay, reliability, bandwidth etc.

· Dynamic algorithm.

· Routing based on type of service.

· Load Balancing (Multiple Line Usage).

· Hierarchical systems support.

· Security against misuse.

· Supports point-to-point, Multi-access with or without broadcast.

· Backbone area (Area 0) with every autonomous system.

· One area to other area traverse through backbone.

· Backbone topology not visible outside.

· Within area link status routing algorithm is used.

· Three kinds of routing: Intra area, Inter area, Inter- AS