Routing Algorithms, Congestion Control, and IPV4 Protocol: A Comprehensive Guide
Distance Vector Algorithm
- A router transmits its distance vector to each of its neighbors in a routing packet.
- Each router receives and saves the most recently received distance vector from each of its neighbors.
- A router recalculates its distance vector when:
- It receives a distance vector from a neighbor containing different information than before.
- It discovers that a link to a neighbor has gone down.
- The DV calculation is based on minimizing the cost to each destination
– In distance vector routing, each node shares its routing table with its immediate neighbors periodically.
Initialization
- Each node can know only the distance between itself and its immediate neighbors, those directly connected to it.
- each node can send a message to the immediate neighbors and find the distance between itself and these neighbors.
- When a node receives a two-column table from a neighbor, it needs to update its routing table. Updating takes three steps:
- The receiving node needs to add the cost between itself and the sending node to each value in the second column.
- The receiving node needs to add the name of the sending node to each row as the third column if the receiving node uses information from any row. The sending node is the next node in the route.
Updating
- The receiving node needs to compare each row of its old table with the corresponding row of the modified version of the received table.
- If the next-node entry is different, the receiving node chooses the row with the smaller cost. If there is a tie, the old one is kept.
- If the next-node entry is the same, the receiving node chooses the new row.
Link State Routing
In link state routing each router must do the following things to make it work:
1. Learning about the neighbors : It accomplishes this goal by sending a special HELLO packet on each point-to-point line. The router on the other end is expected to send back a reply giving its name.
2. Measuring Line Cost : A special ECHO packet is sent over to neighbors that the other side is required to send back immediately. By measuring the round-trip time and dividing it by two, the sending router can get a reasonable estimate of the delay.
3. Building Link State Packets : The packet starts with the identity of the sender, followed by a sequence number and age, and a list of neighbours.
Once the information for the exchange has been collected, the next step is for each router to build a packet containing all the data.
4. Distributing Link State Packets : Flooding is used to distribute the link state packets. Routers keep track of all the (source router, sequence) pairs they see. When a new link state packet comes in, it is checked against the list of packets already seen. If it is new, it is forwarded on all lines except the one it arrived on. If it is a duplicate, it is discarded.
5. Computing the New Routes : With all routers having full set of link state packets, it can construct the entire subnet graph.
Congestion Control in Datagram Subnets
1.The Warning Bit : The warning state is set as a special bit in the packet’s header. As long as the router was in the warning state, it continued to set the warning bit, which meant that the source continued to get acknowledgements with it set. As long as the warning bits continued to flow in, the source continued to decrease its transmission rate
2.Choke Packets The router sends a choke packet back to the source host. When the source host gets the choke packet. It reduce the traffic by x%. It ignore choke packets referring to the destination for a fixed time interval, and check again if there is still the choke packets sent back.
3.Hop-by-Hop Choke Packets A choke packet that affects each hop it passes through. More buffer request for router F at this moment.
4.Load shedding Another simple closed loop technique. When buffers become full, routers simply discard packets.
5.Random Early Detection : RED monitors the average queue size and drops packets based on statistical probabilities.This is a proactive approach in which the router discards one or more packets before the buffer becomes completely full. Each time a packet arrives, the RED algorithm computes the average queue length, avg.
6.Jitter Control : The variation (i.e., standard deviation) in the packet arrival times is called jitter. High jitter, for example, having some packets taking 20 msec and others taking 30 msec to arrive will give an uneven quality to the sound or movie.
The IPV4 Protocol
Version field
Version is a 4 bit field that indicates the IP version used.
IHL field
–Header length is a 4 bit field that contains the length ofthe IP header. –The initial S rows of the IP header are always used. –So, minimum length of IP header — S x 4 bytes — 20 bytes. –The size ofthe 6th row representing the Options field vary from 0-40 bytes. –So, maximum length of IP header — 20 bytes + 40 bytes — 60 bytes.
Type of service field.
to distinguish between different classes of service 6-bit field contained a three-bit Precedence field and three flags, D, T,and R. {Delay,Throughput, Reliability}
Total length field
Total length is a 16 bit field that contains the total length ofthe datagram (in bytes). Total length — Header length + Payload length
Identification field
Identification is a 16 bit field. use to identify fragments of the same frame, Useful in re assembly of fragmented datagrams.
Protocol field
• It tells the network layer at the destination host to which protocol the IP datagram belongs to. • Protocol number of ICMP is 1, IGMP is 2, TCP is 6 and UDP is 17.
Header Checksum
• It contains the checksum value of the entire header. • The checksum value is used for error checking of the header.
Source address and Destination address :
indicate the network number and host number. logical address ofthe sender and receiver ofthe datagram.
Options field :
options is a field whose size vary from 0 bytes to 40 bytes. This field is used for several purposes such as- Record route, Source routing, Padding
Techniques for Achieving Good Quality of Service
1. Overprovisioning – to provide so much router capacity, buffer space, and bandwidth that the packets just fly through easily. 2. Buffering – Flows can be buffered on the receiving side before being delivered. 3. Traffic Shaping – Traffic shaping is about regulating the average rate (and burstiness) of data transmission.
- The Leaky Bucket Algorithm
- The Token Bucket Algorithm
4. Packet Scheduling
- FIFO queuing,
- priority queuing,
- and weighted fair queuing.
IPV4 Header diagram
