Computer Network - Data Link Layer

Maximum data rate

For noiseless channel
If V be the number of discrete level and H be the bandwidth in Hz
maximum data rate = 2H log V
2H samples per second are required to completely reconstruct signals passed through loss pas filter of bandwidth H


For noisy channel
maximum data rate = Hlog(1+S/N)
conversion of S/N ratio to decible  = 10log(10,S/N) (to the base 10)
its irrespective of number of discrete levels

Data link layer
checks error transmission flow control
header and trailer attached to the network packet and called as frame
Ack is not a necessary service for data link its just optimization because instead of requiring n/w layer to send complete pkt again data link layer send the fragments that are not recieved


No Ack connectionless service
appropiate in case of real time traffic like voice where bad data is better than late data. used for less error prone channels

with Ack connectionless service
for unreliable channels like wireless


Framing methods
How do the receiver know in the continuous stream of data different frames
1)character count
2)flag byte with byte stuffing
include flag byte before header and after trailer
for each flag byte include escape character and one for each escape byte in data also
3)
to ensure that frame sequence never appears in the data
to frame sync sequence 01111110 containing six adjacent 1's a 0 bit is stuffed after every five 1's

Error detection and correction

error detecting code ,having enough information to identify error and
error correcting code, having enough redundacy to correct the corrupted data
consider data of m bits and r redundant bits
n = m+r
to detect d error we need distance d+1 code
to correct d error we would need 2d+1 code
 (n+1)2^m <= 2^n where n=m+r

Hamming rule
m+r+1 <= 2^r
this is lower limit on number of bits needed to correct single error in any of the n bits in message
we need to detect error in all the transmitted m+r bits and  
additional 1 is for no error

bits that are power of 2  {1 2 4 8 ...} are check bits rest are filled with data bits
each check bit forces the parity of some collection of bits including itself  A bit may be included in several parity computation

to which check bits the databit in position k contributes
like data bit at position contributes to check bits 1 2 8

A data bit k is checked by those check bits only

Problem A host uses odd parity to compute a hamming code
1)what is hamming code for bit sequence 1011001?

solution

from the hamming rule formula we find the minimum check bits required
it comes as r=4 for this message of size m=7 so total n =11
leave the check bits position which would be 1 2 4 8
and  calculate check bit for each data bit at that position
1 2  3  4  5 6 7 8 9 10 11
--------------------------
_ _  1  _  0 1 1 _ 0  0   1
find the check bits that contribute at each data positions

databit  check bit positions 
-------------------

3               0011
5               0101
6               0110
7               0111
9               1001
10             1010
11             1011

so check bit at position 2^0 forces parity for data bits at position {3,5,7,9,11} ={10101} odd
at position 2^1 to {3,6,7,10,11} = {11101} even
at position 2^2 to {5,6,7} ={011}even
at position 2^3 to {9,10,11} = {001} odd

so check bits at position 2 and 4 are 1
so hamming code is
0111 0 1 10 0  0   1

b)which bit is in error if following hamming code is recieved 0010011
solution
we have to include the check bit itself in parity check here
2^0 bit for {1,3,5,7} = 0101 error
2^1 for {2,3,6,7} = 0111 no error
2^2 for {4,5,6,7} =0011 error

error is in data position  2^0+2^2 = 5

Cyclic redundancy check

for polynomial of degree k include k zero bits at the end of the message m and divide m by polynomial g


upon receiving the checksummed frame receiver divides it by G(x) that is (T(x)+E(x))/G(x) T(x)/G(x) is zero so result of computation is E(x)/G(x) those error that are factor of polynomial will give zero other would give non zero result and would be caught

one bit error with CRC
E(x) = x^i so if G(x) has two or more terms it will give non zero remainder hence detected

Detecting double bit error
G(x) should not divide x^k + 1 for any k up to maximum  length of frame

Data link layer

control information or frame header(info also included)
1)kind whether any data in the frame or not
2)seq and ack


Problem A packet is divided in to 10 frames. chance frame getting correctly at receiver is .80 how many packet transmission required for successful
Solution  probability of successful transmission of packet = 1- .8^10
expected number of tranmission = {1 to infty} i (1-p)^i-1
geometric distribution
value = 1/p


making two changes to any valid code gives another valid code in case of parity so it has hamming distance of 2

MAC

Static channel allocation
if there are N users bandwith is divided in to N equal sized portions
mean time delay T
capacity of channel C bps
arrival rate of frames l frames/sec with mean 1/u bits/frame

service rate that is how many frames the channel can process = C/(1/u) =Cu  frames/sec
T = 1/ (uC - l)
that is when there is contention for channel we get the delay of T

For N subchannels
each with C/N bps capacity
frame arrival rate for each l/N frames/sec
Now T' = 1/(u(C/N) - (l/N))  = NT
that is mean dealy is N times that of single channel delay time

Dynamic Channel Allocation

Pure Aloha
feedback property of broadcasting : that is whenever a station transmits data it will also receive the same data so it has a way to know that if data got corrupted in transmission
terminal transmits whenever they have data to send without worry about collision
if two terminals try to transmit at the same time there will be collision data gets garbled and they need to send data again with random backoff time

Efficiency of Pure Aloha
frame time is the amount of time needed to transmit the fixed length frame
An infinite population of user generate new frames according to a poisson distribution with
mean N frames / frame time
If N>1 then  there will be collision on each transmission, that is channel can handle only 1 frame per frame time
we should have N<1 for reasonable throughput

There will be retransmissions of frame that suffered collision consider probability of k transmission attempts per frame time to be poisson distribution with mean G per frame time. G>= N
at low load G~= N at high loads number of collisons will be high so G>N

If there are N stations in the system
each station transmits with the probability p'
G is Average number of packets in the system
In period time t average packets will be  Np'
In vulnerable period of 2t it would be 2N*p'   //each transmits with p' only but for period of 2t

G' for vulnerable period is therefore 2Np'

Since G is the mean number of packet and from the poisson distribution we can find

Find the probability of k frame transmission give mean G
P[k] that is k packet trammisions occur

Probability that k frames are generated during a given frame time according to poisson distribution is
P[k] = (G^k e^-G)/k! where G is the mean number of frames


Expected number of transmission required for each sent frame = {k 1 to infty} kPk
e^2Np' or e^2G
What is throughput
P probability that a packet is successfully transmitted  //different from p' which is specific to station
Throughput average number of packets that can successfully go through
S = GP that is this fraction of transmitted frames escape collision

Find P, the probability that a packet is successfully transmitted
if t is the time to send frame then 2t is vulnerable period

P = probability of no other traffic during vulnerable period
probability of zero frame P[0] =  e^-Gfor duration of 2t its P[0] = e^-G'
so probability of no traffic during vulnerable period is e^-2G   or e ^-2Np'
and S = G * e^-2G  or
S in term of p' and N is S = Np' * e^-2Np'

When is maximum throughput achieved
Maximum through put is at G =1/2 or when power of  e is =1 by taking derivative wrt G
and is S= 1/2e or .184 so 18% is best channel utilization

Slotted Aloha

divides the time into discrete intervals each of frame time
user need to agree on slot boundaries
data is sent only at beginning of next slot
vulnerability period is halved t only

Probability of  successfully transmitting a packet in vulnerable period is e^-G
Probability of no other traffic in vulnerable period is e^-G which leads to
Throughput S =G e^-G
maximum throughput at G=1 with S =1/e = .368 that is 36.8%

Expected number of transmission required for each sent frame = {k 1 to infty} kPk
Pk probability requiring k transmission is from binomial distribution its
(1-p)^k-1*(p) where p is probability of successful transmission that is without collision
in case of slotted aloha its e^-G so
E = {k 1 to infty} k * (e^-G) (1-e^-G)^k-1  = e^G

Carrier Sense Multiple Access Protocol

stations listens to channel transmission and act accordingly

Persistent and Nonpersistent CSMA
first listen to channel, if busy wait until idle
if collision occurs , station waits random amount of time and starts all over again
1 persistent because transmits with probability 1 when finds channel idle

Cases in which collision can occur
if first station starts sending and second and already started transmission but because of propagation delay first station had sensed channel as free
while third station is transmitting and two stations are waiting for channel to be free they both will start with probability 1 so there will be collision

Non persistenet CSMA
In case of busy channel it doesnot continously sense the channel instead waits random amount of time

p persistent CSMA
applies to slotted channels
in case of idle channel it transmits with probability p and with probability 1-p defers till next slot

CSMA with collision detection

In CSMA stations donot transmit when they detects the channel as busy
In case of collision detection stations aborts transmission if they detect collision
saves channel bandwidth and time

How much time will it take for station to realize there has been collision
consider t to be propagation delay between farthest stations
transmission from station1 reaches station2 at time t0+t  if station1 transmits at t0
now if station2 starts transmitting just before the signal from station1 reaches station2 there will be collision and station2 will find it immediately but it will take 2t-e time to reach station1
So in the worst case a station cannot be sure that it has seized the channel until it has transmitted for period 2t without hearing collision
we model it as slotted aloha with 2t contention period(slot width)
Since station must continually  monitor the channel for collision so CSMA CD with single channel are half duplex because the receiving logic is used in sensing

Collision Free protocol

A bit map method
contention period consists of N slots and jth station sends a 1 in the jth slot if it has data queued for transmission After contention period is over each station is aware of other stations and they start transmitting in numerical order
Performance
low order stations has to wait on average 1.5N slots and
high order stations wait on average .5N slots
the mean for all stations is N slots
overhead per frame is N bits and amount of data d bits then efficiency is d/N+d
at high load its d/d+1

Ethernet

Manchester Encoding
used in Ethernet
to unambigously determine the start end or middle of each bit without reference to external clock
each bit is divided into two equal intervals.
A binary 1 bit is sent by having the voltage set high during the first interval and low in the second
A binary 0 bit is just the reverse low during first and then high.
requires twice as much bandwidth than straight binary encoding
to send data at 10Mbps signal has to change 20million times/sec

Differential Manchester
1 bit is indicated by absence of a transition at start of interval
0 bit is indicated by presence of a transition at start of interval
signal changes in the middle for both

Ethernet MAC protocol
preamble of 8bytes
sender and destination address 6byte address
0 for ordinary address and 1 for group address, group address allows multiple station to listen to single address its called multicast and address of all 1's is broadcast address
there are 48 - 2
type field tell the which process to give frame to according to proctocol name in type
data field is up to 1500 bytes maximum or including the destination and source address its 1518bytes
This doesnot include the Preamble and Start framedelimiter which are total 8 bytes
minimum data length also specified because
1)byte of 0 causes problem of stray bits in the channel so to distinguish valid frames from garbage there is minimum size of 64 bytes for frame and if data portion of frame is less than 46 bytes the padding is done
2)if the stations complete transmission of short frame before the noise burst gets back to it the sender would assume successful transmission only after time 2t can it know if collision occured
so for 10Mbps LAN with cable length of 2500meters , the worst round trip time has been determined as 50microsec Therefore minimum frame should be transmitted for at least this much time
Transmission of a bit on 10Mbps takes 100nsec so smallest frame should have 500 bits and so is the minimum frame for ethernet is 512 bits or 64bytes

So minimum frame size in ethernet including preamble and sfd is 512 + 64 bits

Checksum 32bit hashcode of data only error detection like CRC

Binary exponential backoff Algorithm(in case of collision not when senses channel busy)
After collision time is divided into discrete slots whose length is equal to 2t
After first collision each station waits either 0 or 1 slot times before trying again
After second collision each station waits either 0 1 2 3 at random
After third it would be 0  ..2^3-1

After 10 collisions its fixed at 1023 only if collision still happens and reaches 16 then its reported as failure

the value k that each station chooses depends on which collision number is it for that station

Problem

If two stations A and B collide  at first transmission A wins first backoff transmits successfully and then both tries to send again and collides again what is probability that A wins second backoff
Here slots avaiable for A are 0 and 1 because its 1st round for A
and for B slots available are 0 1 2 3 because its 2nd round for B
So the probability that A wins is if A chooses 0 and B chooses 123 anything or A chooses 1 and B chooses 2or 3
P(A wins) = 1/2 * 3/4 + 1/2 *2/4 = 5/ 8

How transmission in Ethernet works
1)Once it has the ethernet frame it senses the channel
If idle then start transmitting the frame
If channel is busy it must wait until it find the channel idle plus a additional wait of 96 bit times once it find it idle
2)monitors the channel after starting transmission If no signal from other stations found it has successful transmission if it finds the signal from other stations it stops transmission and transmits 48 bit jam signal instead
3)After transmitting the jam signal it enters exponential backoff and chooses the value K at random from 0 to 2^k-1 Then it waits for K*512 bit times and repeats again.

Why is jam signal required
In case B aborts the transmission after detecting transmission from A and has not put enough bits on the line, A may not be able to detect the signal and hence B needs to send jam signal


Performance of Ethernet
k stations are always ready to transmit
if each tranmits during contention period with probability p then probability A that some station acquires the channel is
A = k(1-p)^k-1p

A is maximized when p=1/k with A -> 1/e as k>infty

Expected number of slots per contention  = {j:1 to infty} jA(1-A)^j-1  = 1/A
each slot has duration of 2t the mean contention interval is 2t/A
for optimum value of p, expected number of contentions  =e
and contention interval would be at most 2te = 5.4e

Channel Efficiency
If mean frame takes P sec to transmit
Channel efficiency = P/(P+2t/A)
the longer the cable the longer will be contention interval

P=F/B framelength /bandwidth
A = 1/e for optimal case
t = L/c  , c is speed of signal propagation and L is length of cable

Channel efficiency = F/B/(F/B + 2(L/c)*(e)) = 1/(1+2BLe/cF)

Problem bandwidth C =100Mbps  10000 bits/frame  arrival rate 900frames/sec Delay for average frame?
Solution T = 1/(uC -l) 
mean frame length 1/u = 1/10000 =  10^-4

Problem Let N stations share 56-kbps pure Aloha. Each outputs 1000bit frame on average once 100sec
maximum value of N
Solution
required bandwidth for each station is 1000/100 bit/sec 10bit/sec
In Pure aloha usable bandwidth  is .184*56kbps = 10.3kbps
so N * (bandwidth for each station) = allowed bandwidth
N= 10300/10

In pure aloha, at small load,transmission can start instantly for slotted it has to wait for next slot introducing mean 1/2 slot of delay

Problem 10000 stations compete for slotted aloha channel Average station makes 18request/hour A slot is 125micro sec What is approx total channel load
Solution  Load is number of request in slot time
number of request per sec = 18/3600 = .005 request/sec
total number of request = .005*10000 = 50 request/sec
In slot period of 125micro sec number of request = 50 *125*10^-6 req/sec = 50/8000

Problem All formula  for slotted Aloha
G is number of requests in the vulnerable period = (number of request/sec) * vulnerable period
Solution Probability of success in slotted aloha is e^-G
Probability of success on kth transmission is (1-e^-G)^k e^-G
Expected number of transmission attempts =e^G

Problem In slotted Aloha 10% of slots are idle
1)what is G
probability of successful transmission is .1
so G= -ln P =-ln .1 =2.3
2)channel overload or underload
since G>1 so its overload

Problem If backlogged station donot accept new arrivals at MAC and unbacklogged accepts only single
Consider arrival rate of .05 arrival/slottime at each station by independent process, backlogged attempt retransmission with probability .02 in each slot
1)what is probability of arrival of new frame at MAC of unbacklogged & backlogged station
unbacklogged station will accept only first arrival
Probability of no arrivals = e^G
probability for at least one arrival at unbacklogged  = 1-e^-G  where G is .05
= .05
MAC of backlogged do not accept new arrivals so P=0
2)If there are 20 stations and 5 of them are backlogged what is probibility that one of the backlogged will see successfull transmission
For successful transmission no arrivals should be at backlogged station p= (e^-G)^15 = (1-.05)^15 = .472
For unbacklogged only one of them should transmit that is rest 4 should not transmit(
C(5 1)(1-.02)^4 * (.02)

Backlogged station do not accepts new arrivals at MAC because they donot have buffer So effective arrival rate at medium will decrease as the number of backlogged station increases
Poisson arrival rate is distributed equally at each station so if we arrival rate at medium is l then arrival rate at station is l/m for each m stations

Probability of unbacklogged station to transmit is 1- e^-G
Probability of i unbacklogged station transmit at next slot =
(ways to choose among i unbacklogged stations) (probability of transmitting for i unbacklogged stations)*(probability of not transmitting for remaining unbacklogged station)


Problem How long does a station has to wait before it can retransmit again
1)bit map protocol
assume frame is d bits If stations is the highest numbered
N bit of contention period + period when all N-1 transmits ( when last station wants to send just after its contention slot is gone)
= N + (N-1)*d   (assumption same 1bit for single slot time)

Problem Two CSMA/CD stations are trying to transmit multiframe file After each frame is sent they contend for channel using backoff algorithm
1)What is probability that contention ends on round k
Using backoff exponential algo
At round one they have single slot and they both try to transmit in that and hence collides
At round two there are 2 slots waiting for 0 and 1
At i th round station  can choose to wait in any 2^i-1 slots

Probability of choosing any one slot in ith period is 1/(2^i-1)
probability of both station choosing same slot is (1/2^i-1) * (1/2^i-1) = 1/2^2(i-1)
Total probability of choosing any of the 2^i-1 slot is hence P = 2^i-1 * (1/2^2(i-1)) = 1/2^i-1
this is probability of collision in ith round
for success on kth round we should have k-1 round in collison and kth round on success
that is
{product i:1 to k-1 }(1/2^i-1)  * (1- 1/2^i-1) 

 Problem what is baud rate in case of Ethernet
Solution
Ethernet uses manchester encoding which uses two signals to represent a bit so baud rate is 2 times the data rate because it has 1/2 bits/signal. In case of binary encoding baud rate = data rate
so for Ethernet 10mbps it should be 20megabaud

Problem Consider node A and B on the same 10Mbps Ethernet, propagation delay between two nodes is 225bit times
1)Node A starts transmitting and before it finishes node B starts transmitting .Can a finish transmitting before it detects that B has transmitted
The first bit from A reaches B at t=225 In the worst case B starts transmission at t=224 this transmission would reach A at 224+225(sent from B) =449 Since minimum frame size is 512+64 bit times A should be still transmitting and would detect collision
2)Suppose A and B both sends frame at the same time, the frames collide and then both chose different values of K in CSMA/CD Can retransmission collide Assume A chooses K=0 and B K=1?
Solution
At t=0 A and B starts transmitting
At t=225 both hears each other signals and start transmitting jam signal which is 48 bit time so
At t=225+48=273 both finishes transmitting jam signal, last bit of jam signal takes another 225 bit time to reach A and B
Immediately after sending the jam signal A B starts in exponential backoff
At t=273 A starts sensing the channel for transmission and B waits for 1*512 bit time that is 273+512=785  
A waits for the jam signal from B to reach it
At t=273+225=498 jam signal from B reaches A and A finds the channel idle and now before transmitting A has to wait for 96 bits
At t=498+96=594 A starts transmitting
A's first bit would reach B at 594+225 =819
so B would find the channel idle at 785 and would start wait in 96 bit period that is 881
At t=819 B would find signal from A and would not transmit

Problem Consider CSMA/CD network with 1Gbps over 1km cable. The speed of signal is 2*10^5km/sec.What is the minimum frame size
Solution propagation time = 5microsec
RTT = 10microsec
It should transmit for at least RTT period that is 1Gps*10microsec = 10^9 *10*10^-6 = 10000bits


Baud and Bit rate
Baud rate is signal /sec while bit rate is bits/sec
bit rate = baud rate * bits/signal

If we are using 1 bit per signal its same
If we are using
Baud rate in case of serial data transfer baud rate = bit rate single bit is used to represent signal
1 start bit 1/2 stop bit 0/1 parity bit for serial communication asynchronous
Example
1)calculate overhead for data size 7 bit ,1stop and no parity
overhead = 2/9 *100
2)represent 0101 1010 with 1 stop and no parity
start bit represented with 1 bit and stop with 0
1 0101 1010 0
3)time to transfer 4Mbits at 9600 baud rate
since in serial communication baud rate = bit rate we have
time = 4Mbits/9600 sec =

Stop and wait protocol

Line utilization is 1/(1+2a)   or transmission time/ (transmission+RTT)
L packet size and  u bandwidth
transmission time = L/u
a= propagation time / transmission time
transmission time is time to transmit a frame

Sliding window

Link utilization
1             when n >1+2a
N/1+2a   else


Problem Consider one way propagation time of .35sec, transmission rate of 1Mbps, and packet of 1000 bits ack time negligible
1)minumum timeout period for stop and wait ARQ

Timeout from end of the packet is 2*propagation delay
if we consider from start of packet it will add tramission time to this qunatity
2)minimum window size for go-Back N for 100% utilization assuming no errors?
window should be sufficiently large so as to transmit for the period until ack recieved
N /(1+2a) >=1
N >= 1+2a
frame transmission time = 1000/10^6 sec = 1ms
propagation time = .35
a= .35/10^-3 =  350

N = 701

Problem Consider 10Mbps bandwidth with propagation delay of 270ms and frame size of 10K-bit What is link utilization for stop and wait ARQ assuming probability of single frame error =10^-3
Solution line utlization = (1-P)/(1+2a)
For goback N its
N(1-p)/(q+2a)(1-p+Np)



Token Ring
Token cirulates in the ring topology LAN
when station wants to transmit data it converts token into data frame and start transmission at last it converts it in token back and circulates it in the ring
At each station a delay is introduced on data transmission
Release after transmission

Ring latency number of bits that can be in transit simultaneously or time for bit to circulate ring

Reinsertion strategies
1)Multi-Token operation: Free token transmitted immediately after the last bit of data frame ,that is, as soon as station has transmitted its data it will release free token
2)Single-Token operation: free token is inserted after last bit of busy token is received back that is free token is independent of data frame and depends on the ring length
If frame is longer than latency then that would mean busy token is recieved and its still transmitting so station would release free token when last bit of data frame is transmitted like multi token
3)Single frame operation
free token inerted when last bit of transmitted frame is received back at station

utilization = 1/ (1+a/N)
X maximum frame transmission time allowed per station
Throughput
Multi token



Problem consider a ring topology LAN with total length 2d with two stations d apart Ack is recieved by circulation of packet itself There are N=10 other stations on the ring each introduces delay of 1 bit
Solution
1)find the 1bit delay that is howlong is delay at each station in seconds
1Mbps is capacity so it would take 1microsec delay
2)total delay for N+2 stations = 12microsec
3)find how long it takes for 100 bit packet to fully circulate the ring and return to sender
propagation delay is 2d*5microsec = 10microsec Adding one bit delay gives 22microsec to fully circulate distance of 2d
4)transmission time of host 100/1M = 100microsec
5)host A will recieve the last bit at 122microsec for 100 bit packet
6)so for 10000 packets it would take 10000*122 = 1.22sec

Problem Consider there are N stations in token ring LAN Frame size is L bit, RMbps speed ,b bits latency per adapter d m between each stations with v speed find effective transfer time for all 3 strategy
Solution
1)Reinsertion after completion of transmission or Multi-Token operation
that is token is inserted after the transmission is complete
time to pass token to next station =  propagation time + bit latency delay, assuming token transmission time negligible
effective transmission time = frame transmission time + time to pass token to next station
                                        = L/R + (d/v+b/R)
Efficiency = L/R /(L/R+(d/v+b/R))

2)reinsertion after return of token or Single Token operation
where token is inserted after last bit of busy token is received back or if transmission is still in progress then when busy token is received then after transmission ends

Effective time = Max(frame transmission time,ring latency ) + time to pass token to next station
ring latency = time required for bit to circulate ring = N(d/v+b/R)
                   = Max{L/R,N(d/v+b/R)} + (d/v+b/R)
3)Reinsertion after return of frame or Single frame operation
time for last bit of frame to reach back to station = frame transmission time + ring latency
Effective transmission time = frame transmission time + ring latency + time to pass token to next station
Effective transmission time = L/R +  N(d/v+b/R) + (d/v+b/R)

Throghput
1)Single Frame
effective time = frame transmission X + ring latency τ'
consider normal ring latency a' = τ'/X
ρmax =  MX/(M(X+τ') +τ') = 1/(1+a'(1+1/m))
1)Multiple token
effective time = frame transmission X + ring latency τ'
consider normal ring latency a' = τ'/X
ρmax =  MX/(M(X+τ') +τ') = 1/(1+a'(1+1/m))


If each station transmits up to k frames/token Maximum throghput ?


References

nptel.iitm.ac.in/courses/.../Computer%20networks/pdf/M3L2.pdf

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/