Routing and Congestion Control
Routing and Congestion Control
Routing and Congestion Control
The network layer is the layer above the data link layer and below the transport layer in the OSI model. The need for
the network layer arises when two end systems are attached to different networks . In such cases there has to be a
method to identify separate networks .Moreover these two networks may be a part of the large internet work .So, there
has to be routing mechanism to find out the best part from source to destination machine. Hence , the basic purpose of
the network layer is to send packets from source machine all the way to destination machine
Logical Addressing: Distinguish between networks and separate them form each other
Routing: Identify the best path between source and destination and create such path using switching technique
Design Issues
The network layer routes the data from source to destination using switching , addressing and routing .
Packet Switching
Need of Switching:
1) 2 end systems belong to same or different networks
2) A Subnet or a network cloud separates them.
3) The source sends a packet to nearest Router/ Switch on its own network
4) The packet is stored there, verified and forwarded ahead to the nest router.
5) This is called as “Store and Forward― switching
6) Packet Switching can be achieved in 2 ways:
Connectionless Service: Datagram Packet Switching
Connection Oriented Services: Virtual Circuit Packet
Switching.
Page 1
Services Provided to the Transport Layer
1) The transport layer has to be shielded from the heterogeneity of the networks
2) Hide number, type and topology of the routers in the subnet
3) The addressing scheme designed by the network layer and provided to the transport layer should be uniform across all
the types of networks.
4) The services provided (connectionless or connection oriented) should be independent of the router technology.
Logical Addressing
The important job of the network layer is to find destination address.
2) Each machine has a MAC address called as physical address, which is the address of the NIC of the machine.
3) MAC address is independent of networks and are unique.
4) Logical addressing is network dependent and global.
5) It helps identify the network in which the machine belongs.
6) IP addressing is a logical addressing used in TCP/IP protocol.
Page 2
IPv4 Addresses
The IP address used in internet is a 32-bit long address .This address is unique and universal. No two machines on
the internet can have the same IP address.
Binary :
4 byte = 32 bit address
Ex: 10101010.10101010.10101010.10101010
This must be exactly 32 bits
Only 0 & 1 is allowed.
Classful Addressing
• The address space is divided into classes.
• There are 4 classes namely A B C D & E
• Now a days classless addressing is used.
• In binary the first few bits and in decimal the first number identifies the class
Classes
• Class A : First Byte 0 or First Decimal 0 – 127
• Class B : First Byte 10 or First Decimal 128 – 191
• Class C : First Byte 110 or First Decimal 192 – 223
• Class D : First Byte 1110 or First Decimal 224 – 239
• Class E : First Byte 1111 or First Decimal 240 - 255
Netid is 8 bit(First bit is 0) Netid is 16 Bit (First 2 bits are 10) Netid is 24 Bit (First 3 bits are 110)
Hence there can be 128 Hence there can be 214 networks Hence there can be 221 networks
networks (netid 0 to 127)
Page 3
Address Mask:
• The router outside the network has a default mask to identify a network and route the data.
• The default mask is a 32 bit address with all netid portions containing 1’s and hostid 0’s
• The router looks at the first byte and identified the class and applies mask. (AND)
Network Address:
• The network address is different than Netid.
• It is netid and hostid with all the hostid bits as 0’s
• Ex: 109.0.0.0, 164.25.0.0, 200.11.8.0 etc.
Wastage of addresses:
• The classful scheme is fixed address scheme.
• This results in wastage of addresses.
• EX: Organization having 20 hosts will take class C address and 236 addresses will be waste.
• Hence classless addressing is used.
Classless Addressing:
• Classful is fixed addressing scheme, hence there is a lot of wastage of address
• Hence classless addressing is implemented.
• Here addresses are assigned in blocks, however there aren’t any classes.
• The addresses must be contiguous
• The number of addresses must be power of 2
• The first address of the block must be divisible by the number of addresses.
Page 4
Using Private IP:
• A network is assigned a single IP address.
• All machines within the network are assigned a private IP and use the same while communicating internally.
• While communicating with the outside world they use the Public IP address assigned to them.
Address Translation:
• An address translation takes place between the private IP address and the public address.
• All the outgoing packets go through the NAT translator which replaces the private source address with the public
IP.
• All the incoming packets are received by the NAT router which replaces the public IP by the private IP address.
• The NAT router maintains a translation table.
• The table contains a mapping between the private and public address.
• The translation table also stores the port address of the private IP addresses.
Private address Private port External address External port Trasport Protocol
IPV4 Datagram:
• The internet packet in the IP layer is called as IP datagram.
• The size of the datagram depends on the application that sends data.
• It can contain data form single byte to 65536 bytes.
• The header can be 20 to 60 bytes in length.
Fields in Datagram:
• VER (Version): Defines the version IPv4 or IPv6
• HLEN: Defines the length of the header in multiples of 4. The 4 bits will represent numbers between 0 to 15 which
is then multiplied by 4 to get the header size.
• Type of service (TOS): This is 8 bit defines how to handle the datagram? 3 bits define the priority and 4 bits define
the TOS. TOS are
– D Minimize Delay (Ex: Telnet and Rlogin)
– T Maximum Throughput (Ex: FTP)
– R Maximum Reliability (Ex: Network management and Routing)
– C Minimize cost.
• One of these bits can only be turned on. All 0’s represent normal service.
• Total length: This defines total length of IP (Header+ Data) This is 16 bit field, hence the maximum is 65535.
• Identification: 16 bit field used in fragmentation. Data gram is divided in fragments to match the network size.
This field carries the sequence numbers.
• Flags: 3 bit field defines whether the datagram can be fragmented or not. The flags are D and M. D = Don’t
Fragment and M = More. Value o indicates last fragment.
• Fragment offset: 13 bit field is used as a pointer that shows offset of the data in the original datagram that is
fragmented.
• Time to Live (TTL): 8 bit field indicates the number of routers the datagram can pass. It is initialized by the sender
by some value and decremented by the router. Once this becomes 0 the datagram is thrown away and the sender
is notified with message.
• Protocol: This indicates the upper layer protocol such as TCP, UDP etc.
Page 5
• Header Checksum: 16 bit field used to check the integrity of the header ONLY.
• Source & Destination IP address: Each address field is 32 bit.
• Options: This field is of variable length and allows the packet to request special features such as security level,
route etc.
Checksum:
• This is used for error correction.
• This is calculated on the header of the data and not on the data.
• This is an error detection method.
Options:
• IPV4 datagram contains a fixed part of 20 bytes and a variable part of 40 bytes (Max = 60)
• There are 2 types of options
– Single byte options
– Multiple byte options
Routing :
Routing is one of the important tasks of the network layer. The network layer has to perform routing to deliver packets
from the source machine to the destination machine in an internetwork.
Routing protocols use routing algorithms to build and maintain routing databases or tables and determine which route to
use when forwarding packets.
• Correctness: Subnet must decide the correct path between the source and destination.
• Robustness: Must be able to survive failure of hardware and software, changes in topology, traffic in the network
and ensure that the network works smoothly.
• Stability: It must perform consistently and deliver correct results. Must also respond to good news and bad news.
• Fairness: Every host must be given an equal opportunity to transmit the data.
• Optimality: Must utilize the maximum channel bandwidth. Also make use of all the paths available in the network.
Page 6
Types of routing algorithms:
Routing algorithms can be classified into two types depending upon the way routing decisions are made.
Rounting Algorithms
Non adaptive algorithms: These are static routing algorithms. They do not calculate the route based on the current
network traffic and conditions. Routes are decided in advance and do not reflect the changes in the network.
Adaptive algorithms: These are dynamic routing algorithms. They adapt according to network conditions.
Congestion Control:
• Congestion is a situation in which the number of packets in the network are greater than the capacity of the
network.
• Packets will be discarded due to non availability of buffers. Sender will retransmit the data adding to the
congestion.
• At high congestion, the network packets will not be delivered and the network will fail.
Causes of congestion :
1. Insufficient memory to hold packets within an intermediate processor will cause packets to be discarded.
The sender will retransmit, thereby increasing the no. of packets.
2. Slow processors can cause congestion. If the intermediate processors process packets very slowly or do
tasks like route calculation and table updation slowly, queues will build up.
3. Low-bandwidth lines will allow less packets to move per unit time,thereby increasing propagation delay
for the others.
4. Failed routers or processors due to which there is excessive load on other routers in the network.
5. Excess traffic to some specific host of the network .
Congestion control:
Page 7
• Good retransmission policy is required for optimal efficiency.
• Good sliding window protocol is required so that retransmission is less and many packets can be sent.
• Use piggybacking so that excess traffic can be minimized.
• Good discarding policy is required to determine which packets to discard and when.
Closed loop congestion control:
• This will try to remove the congestion once it occurs.
• This mechanism monitors the network through feedbacks and takes corrective actions.
• Monitoring of system is done. Parameters used to monitor are average delay, %tage of packets discarded, no of
retransmissions etc.
• Transfer the information to the point where the action needs to be taken.
• Adjustment of the operation to adjust the network.
• Transport Layer:
• This takes care of process to process delivery where as data link takes care of node to node delivery.
• The issues are same as data link layer.
Routers work independently of the lower layer protocols and only deal with interconnect
Page 8