Network Layer - Routing

Transport layer provides service between two processes running on different hosts
network layer provides service between  hosts
network layer of sending host transfers packet to nearby router, which switches packet from inbound link to outbound link

Functions of network layer
Path determination: Network layer must determine the path taken by packets as they sent.The algorithms to calculate path are called routing algorithm
Switching:The router must move the inbound packet to outbound link
Call setup: Protocols like ATM requires a handshake before sending packets similar to transport layer handshake

Network layer service classification
Network layer service can be provided as either Datagram service or Virtual circuit service.

Virtual Circuit(connection oriented service)
VC setup : sender specifies the destination address to its n/w layer. The n/w layer determines the path , updates the path in each packet switch and may also reserve the resources
Data Transfer
VC termination Sender informs n/w layer which in turn informs the end system and updates the table on the path in packet switch to reflect that VC no longer exists
In connection setup window size maximum packet size data rate timer values like can be negotiated
File transfer Remote login Video on demand are applications that needs connection oriented service
There are situations in which connection oriented service can tranmit packet out of order for example in case of user termination signal

Unlike transport layer in which connection setup only involves two end systems here in n/w layer all the packets switches in the path are also involved

Datagram(connection less service)
Sender informs the n/w layer which attaches the destination address to packet(unlike VC) and moves packet in the network. so packets may follow different paths because routing table may have modified
Best effort service, timing between packets is not guaranteed to be preserved also delivery of the packet is not guaranteed
short burst applications like user verification, fund transfer uses datagram service

Routing Principles
Determines the path that packets are to follow

Routing Algorithm
Problem definition Given a set of routers, with links connecting them Find optimal path from source to destination
Global Routing Algorithms Least cost path is determined using complete knowledge about the n/w. The algorithm takes the connectivity between all nodes and all costs as input
Calculations can be done at centralized location or can be replicated at multiple sites
Also called link state algorithms

Decentralized Algorithm
No node has the complete information, each node has knowledge of only its directly attached links and then through iterative process of calculation and exchange of information with its neighboring nodes  it calculates the path
also called Distance vector algorithms as only direction is known to each node to which it needs to forward packet


Link state routing Algorithm
each node broadcasts the cost of all its attached links
Now each node has identical and complete view of the system
each node can run the algorithm and compute same set of least cost path as other nodes

Dijkstra Algorithm
computes least cost path from one node to all other nodes
for non negative edge path cost only
After kth iteration of algorithm the least cost path are know to k destination nodes and among the least cost paths to all destination nodes the k path will have k smallest cost
c(i,j) link cost from node i to node j, if not directly connected its infinity
c(i,j) = c(j,i)
p(v):  neighbor of b on least cost path to v

Steps

Initially
mark source node as current node and make it permanent node
mark each neighboring node with distance from A
Examine all tentatively labeled nodes and make one with smallest permanent and call it new current node

 After first initialization
1)Examine all adjacent nodes to current node
2)If  sum of label on the current node + distance to neighbor node  <  label on neighbor node
  relabel the neighbor node to new distance from current node
3) check all tentative nodes in whole graph
4) mark one with smallest distance permanent

Complexity of algorithm
In the first iteration we need to check n nodes to find minimum
In the second iteration we check n-1 nodes to find minimum
so it has n(n-1)/2

Distance Vector Algorithm
Asynchronous iterative self terminating distributed algorithm
Each node has a distance table in which rows are all destinations in n/w and columns are directly attached neighbors

D_x(y,z) = C(x,z)+min(D_z(Y,w))
X  Distance table shows that X can reach Y through Z with cost D(Y,Z)
Bellman ford algorithm
graph with negative edge weights
If graph contains negative cycle i.e sum of weights on cycle comes to be negative then there can be no shortest path
Bellman ford can detect negative weight cycles and report their existence but cannot produce correct result if negative cycle is reachable from source

Link cost changes and failures
when a node X detects change in cost form itself to its neighbor Y it updates the distance table and informs the neighbor Z if minimum cost path has changed
neighbors Z updates its cost to X from Y and informs its neighbors if it has changed minimum cost path
It informs X again in case minimum cost path has changed and X updates its table and it continues

1)node Y updates its distance to X to be 60 it checks its minimum cost path to X has changed from 4 to 6 that is minimum cost path is available from Z to X with cost of  6, so it updates its neightbours
2)Z updates its minimum cost to Z via Z its 1+ new min cost that is 7. Z sees that it has new minimum cost it updates its neighour
3)Y gets update from Z that it can reach X in 7 so Y updates its table and so on ..
This problem is called count to infinity
 Y and Z will exchange data and update their cost to X until the cost from Z to X via Y becomes greater than 50


Comparision of Distance vector and link state
Message complexity Link state O(nE) message are sent to let every node know cost of each link
DV algorithm requires message exchange between directly connected nodes at each iteration
Convergence Link state suffers from oscillation while DV can converge slowly and suffers count to infinity
Roubutness

Internet protocol
IP is unreliable(no guarantee that packet reaches destination) and connectionless(no state information about successive datagram) protocol

IP header
normal size is 20bytes unless options are present
 bits are transmitted in big endian format that is 0-7 8-15 .. which is network byte order in TCP/IP
fields
Ip version
header length(4 bit) : 32 bit words in header including options, limits size of ip header to 60byte
TOS(4bits):
minimum delay Telnet Rlogin FTP control TFTP .. interactive applications for small amount of data
maximum throughput :FTP file transfer .... any bulk data transfer
Maximum reliability : routing protocols SNMP
Minimize monetary cost :usenet NNTP
total lenght(16 bit): length of IP datagram in bytes so maximum 65535 bytes, this field changes when datagram is fragmented
a host is not required to recieve a datagram larger than 576bytes
required field because some datalink layer protocols pad small frames to be of minimum length so to know th boundry

identification field uniquely identifies each datagram sent by host
TTL upper limit on number of routers though which a datagram can pass, decremented by 1 by each router that handles the datagram, when this field reaches zero datagram is thrown away, prevents the datagram from getting caught in routing loop forever
header checksum is calculated over IP header only unlike TCP and other protocol.



IP addressing
host has single interface while router has multiple interfaces, each inteface has its own IP address.no two interfaec have same IP address
each interface belongs to a networks and shares that network address the host part specific interface
32 bit long

Token Bucket


Problem Give global distance vector table when

1) each node knows distance to only its neighbors

table contains only entries of neighbors 

2)each node has reported information it had in previous step to its neighbors

each node now knows about its neighbors neighbor like A now knows of distance to E and F

3) same step is performed again

each node now knows about all nodes since there are no more that third level neighbors



2)each node shares the above information with its neighbors ----------- each node knows about its neighbor neighbors

Sockets
connect
sends SYN
called from client
connect return when error or connection estabilitsed
error
no response to syn
rst sent by server hard error
ICMP error soft error

Bind
no need to call bind from client
binds IP and port
if not called ephemral port is choosen
server has to bind some reserved port for it
if server not binds IP, use that which is in client packet as destination IP

listen
called on server
state from - closed to listen

accept
returns next completed connection`

Problem How many class B networks and hosts are possible
Solution
Class B has 16 bits for netid out of which 2bits are fixed and 16bits for hostid
number of networks = 2^14 - 2 (leaving all ones and all zeros also)
number of hosts = 2^16 -2

Problem If delay are recorded as 8 bit number, 50 routers in n/w distance vectors are exchanged twice/sec then how much bandwidth per link is used in both direction
Solution
Length of each distance vector exchanged between routers is 50*8bit
this is the information about all the destinations and minimum distance to them shared by each router with its neighbor
Now for a link a distance vector is shared by both routers
there are 2distance vector exchanged per second by each router so for a link total 4 distance vetors would be shared in both directions so usage is 1600bits/sec

Problem Consider 6Mbps network regulated with token bucket which is filled at rate of 1Mbps Its initially filled with 8Mbits How long can computer transmit at full 6Mbps
Solution Lets S be the time interval for which it transmits at full 6Mbps
For this time the total bits transmitted = Tokens consumed in this period
total bits transmitted in S is 6Mbps * S sec
total number of tokens consumed during S = tockens already present in bucket + tokens generated in time S
 = 8Mbits + 1Mbps*S
so 6S = 8+S
S=1.6

Problem

Problem
http://www.seas.gwu.edu/~cheng/232/