The Network Layer

UNIT 3

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Network Layer:

​

Switching, Logical addressing – IPV4, IPV6; Address mapping – ARP, RARP, BOOTP and DHCP–Delivery, Forwarding and Unicast Routing protocols.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Position of Network Layer

​

N/w layer provides services to TL

​

​

N/w layer takes services to DLL

​

​

Transport Layer

Network Layer

Data Link Layer

Duties of N/W Layer

Inter Networking

Addressing

Fragmenting

Packetizing

Routing

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Network Layer Design Issues

• Store-and-forward packet switching
• Services provided to transport layer
• Implementation of connectionless service
• Implementation of connection-oriented service
• Comparison of virtual-circuit and datagram networks

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Store-and-Forward Packet Switching

The environment of the network layer protocols.

ISP’s equipment

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Store-and-forward packet switching:

• Carriers equipment is used to send the data from router to router.
• N/W Layer is responsible for carrying the packets from source to destination i.e it is responsible for host-to-host delivery.
• The n/w layer receiving the services from DLL and providing the services to the transport layer.
• The services provided at the n/w transport layer interface. The interface acts as a medium b/w the carriers equipment and customers equipment. In the above fig carriers equipment is shown inside oval and the customers equipment is shown outside the oval.
• The job of carrier’s equipment is to send all the packets passed by the customer i.e host h1 is directly connected to carriers router ‘A’ by a leased line and h2 is on LAN with a router operated by the customer.
• In every router the packet is stored and calculates the check-sum of every packet and verify it, then it is forwarded to the next router until it reaches its destination host where it is delivered. This mechanism is called store-and-forward packet switching.

​

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Circuit Switching:

• It establishes a physical path between sender and receiver of the message, before a message is delivered. When a connection is established b/w sender and receiver, the entire message travels through the established path from sender to receiver.
• Once the message is delivered to the receiver the source informs the network about the completion of transmission and all the switches release.
• Circuit switching is always implemented at physical layer.
• Circuit switching can be implemented using 2 technologies
• Space Division Switching
• Time Division Switching

It is not flexible because once the path is set all the paths of the transmission follows the same path.

Ex: Telephone conversation

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Packet Switching:

• It is a connection-less technology. It does not establish any physical connection before the transmission starts.
• In packet switching before the message is transmitted it is divided into some manageable parts called packets. These packets are routed one by one from source to destination.
• In packet switching each packet message follow a different route to reach destination.
• The packets are arrived at the destination are out of order but they are assembled in order before the destination forwarded to the upper layer.
• It is always implemented in N/W layer
• It has two approaches i) Datagram Approach

ii) Virtual Circuit Approach

It is a store and forward technique.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Properties of Routing Algorithm:

• Correctness and Simplicity:

The packets are to be correctly delivered or not.

• Robustness:

Ability of the n/w to deliver the packet via some route even in the phase of failure.

• Stability:

The algorithm should maintain stability or equilibrium in the phase of change in conditions in the n/w.

• Optimality:

Obvious requirements

• Efficiency:

Minimum overhead

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Services Provided to the Transport Layer

1. Services independent of router technology.
2. Transport layer shielded from number, type, topology of routers.
3. Network addresses available to transport layer use uniform numbering plan
1. even across LANs and WANs

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Implementation of Connectionless Service

Routing within a datagram network

ISP’s equipment

A’s table (initially) A’s table (later) C’s Table E’s Table

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

• In this connection-less service the packets are injected into the subnet individually and routed independently of each other i.e no connection is established.
• The packets are called as datagrams and the subnet is called as datagram subnet.
• Let us assume that process p1 has long message for p2 so the n/w layer has break into 4 packets and sends each of them in router ‘A’ using some point-to-point protocol.
• In the carrier’s equipment every router has internal routing table , telling it way to send the packet for each possible destination.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Implementation of �Connection-Oriented Service

Routing within a virtual-circuit network

ISP’s equipment

A’s table C’s Table E’s Table

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

• In connection-oriented service, we need virtual circuit subnet.
• Virtual circuits are used to avoid to choose a new route for every packet sent.
• When a connection is established a route from the source machine to destination machine is chosen as connection setup and stored in routing table inside the router. When the connection is released the virtual circuit is also terminated.

​

• A’s Table

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Comparison of Virtual-Circuit �and Datagram Networks

Comparison of datagram and virtual-circuit networks

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IP Addresses

1. An IP address, or simply an "IP," is a unique address that identifies a device on the InternetAn IP address, or simply an "IP," is a unique address that identifies a device on the Internet or a local network.
2. Two versions:
• IPV4:
• four sets of numbers from 0 to 255, separated by three dots
• Example:67.43.14.98
• 4,294,967,296 possible IP addresses
• IPV6:
•  It contains eight sets of four hexadecimal digits and uses colons to separate each block.
• Example:2602:0445:0000:0000:a93e:5ca7:81e2:5f9d
• 3.4 x 10³⁸ or 340 undecillion) possible IPv6 addresses

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IP Addresses Classes

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IPV4 Header

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

• Version: The first header field is a 4-bit version indicator. In the case of IPv4, the value of its four bits is set to 0100, which indicates 4 in binary.
• Internet Header Length: IHL is the 2nd field of an IPv4 header, and it is of 4 bits in size. This header component is used to show how many 32-bit words are present in the header. As we know, IPv4 headers have a variable size, so this is used to specify the size of the header to avoid any errors. This size can be between 20 bytes to 60 bytes.
• Type of Service: ToS is also called Differentiated Services Code Point or DSCP. This field is used to provide features related to service quality, such as for data streaming or Voice over IP (VoIP) calls. It is used to specific how a datagram will be handled.
• Explicit Congestion Notification: ECN is used to send notifications to the sender or receive in situations where network congestion happens. This is an optional feature of IPv4 can; if one of the endpoints don’t support it, it is not used.
• Total Length: This field’s size is 16 bit, and it is used to denote the size of the entire datagram. The minimum size of an IP datagram is 20 bytes, and at the maximum, it can be 65,535 bytes.
• Identification: The identification or ID field in a packet can identify an IP datagram’s fragments uniquely. Some have suggested using this field for other things such as adding information for packet tracing etc.

​

​

​

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

• Flags: flag in an IPv4 header is a three-bit field that is used to control and identify fragments. The following can be their possible configuration:
• Bit 0: this is reserved and has to be set to zero
• Bit 1: DF or do not fragment
• Bit 2: MF or more fragments.
• Fragment Offset: This field is 13 bit long in length, and it is measured by blocks that units of 8-byte blocks. These are used to specify the offset of a fragment relative to the start of the IP datagram, which when it was not fragmented.
• Time to live: Time to live (or TTL in short) is an 8-bit field to indicate the maximum time the datagram will be live in the internet system. The time here is measured in seconds, and in case the value of TTL is zero, the datagram is erased. Every time a datagram is processed, it’s Time to live is decreased by one second. These are used so that datagrams that are not delivered are discarded automatically. 

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

• Protocol: This is a filed in the IPv4 header reserved to denote which protocol is used in the later (data) portion of the datagram. For Example, number 6 is used to denote TCP and 17 is used to denote UDP protocol.
• The header’s checksum: The checksum field is of 16-bit length, and it is used to check the header for any errors. The header is compared to the value of its checksum at each hop, and in case the header checksum is not matching, the packet is discarded.
• Source Address: It is a 32-bit address of the source of the IPv4 packet.
• Destination Address: the destination address is also 32 bit in size, and it contains the receiver’s address.
• Options: This is an optional field of the IPv4 header. It is used only when the value of IHL is set to more than 5. These options contain values and settings for things related to security. Record route and time stamp etc.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

The IP Version 4 Protocol (1)

The IPv4 (Internet Protocol) header.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

The IP Version 4 Protocol (2)

Some of the IP options.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IP Addresses

IP address formats

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IP Addresses

Special IP addresses

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IP Version 6 Goals

• Support billions of hosts
• Reduce routing table size
• Simplify protocol
• Better security
• Attention to type of service
• Aid multicasting
• Roaming host without changing address
• Allow future protocol evolution
• Permit coexistence of old, new protocols. . .

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IP Version 6 (1)

The IPv6 fixed header (required).

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Internet control messages

1. ICMP(Internet Control message protocol)
2. ARP(Address Resolution Protocol)
3. RARP(Reverse ARP)
4. Bootstrap Protocol (BOOTP)
5. Dynamic Host Configuration Protocol (DHCP)

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

ICMP

  Internet Control Message Protocol (ICMP) is used for reporting errors and performing network diagnostics. In the error reporting process, ICMP sends messages from the receiver to the sender when data does not come though as it should.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

9.32

ARP (Address Resolution Protocol)

• Address Resolution Protocol (ARP) is one of the major protocol in the TCP/IP suit.
• The purpose of Address Resolution Protocol (ARP) is to map an IPv4 address (32 bit Logical Address) to the physical address (48 bit MAC Address).
• Network Applications at the Application Layer use IPv4 Address to communicate with another device. But at the Data link layer, the addressing is MAC address (48 bit Physical Address), and this address is burned into the network card permanently.
• The purpose of Address Resolution Protocol (ARP) is to find out the MAC address of a device in your Local Area Network (LAN), for the corresponding IPv4 address, which network application is trying to communicate.

ARP Protocol

1. The term address resolution refers to the process of finding an address of a computer in a network

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

9.34

Figure 9.6: Position of ARP in TCP/IP protocol suite

9.35

Figure 9.7: ARP operation

9.36

ARP packet format

Hardware Type: This is to specify the type of hardware used by the local network to transmit the Address Resolution Protocols message. Once common hardware under this category would be the ‘Ethernet’ with a value equal to 1, and field size would be 2.

Protocol Type: To assign a fixed number in this field, IPV4 has a number 2048.

Hardware size: This is the length in bytes for the MAC address; generally, we see the ethernet has a MAC address of 6 bytes long.

Protocol Size: It represents the length of the IPV4 logical address, IPV4 address re generally 4 bytes long.

OpCode: This is the length of the logical address in bytes; it specifies the nature of the ARP message. An ARP Request has an assigned value of 1, whereas the ARP reply holds the value of 2.

Sender MAC address: Layer 2 address for the device sending the message.

Sender IP address: Protocol address in IPV4 for the device sending the message.

Target MAC address: Layer 2 of the intended receiver. This field does not hold any value during the request phase and works only during the reply phase.

Target IP address: This address the protocol address for the intended receiver.

​

​

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

ARP vs RARP

ARP: Address Resolution Protocol is a protocol used to map an IP address 32-bit to a physical MAC address 48-bit. The MAC address is known as the hardware id number. This is important in local area networks where devices need to know each other MAC addresses to communicate easily at the data link layer.

RARP: Reverse Address Resolution Protocol is used to map a MAC address 48-bit to an IP address 32-bit. This protocol is typically used by devices that know their Media Access Control address but need to find their IP address.

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

DHCP�Dynamic Host Configuration Protocol (DHCP) is used to dynamically assign Internet Protocol (IP) addresses to each host on your organization‘s network.��The DHCP process can be explained using the acronym DORA, which stands for Discover, Offer, Request, and Acknowledge. 

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

DHCP Process

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

How to configure DHCP Server

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Bootstrap Process

1.  to automatically assign an IP address to network devices from a configuration server. 
2.  Bootp is static, but DHCP is static and dynamic. 

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

BOOTP vs DHCP

Routing

Routing is the process of selecting the best path for data to travel across a network, from one device to another.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

�Routing Algorithm Metrics:

​

• Routing algorithms use many different metrics to determine the best route.
• Path Length
• Hop Count
• Routing Delay
• Band Width
• Load
• Communication Cost
• Reliability
• Path Length: It is the most commonly used routing metric. In some routing protocols allow n/w administrator to assign arbitrary cost to each n/w link.
• Path length is the sum of the cost associated with each link traverse.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

• Hop count: These metric specify the no of passes through internetworking products such as routers i.e the packet must pass through in a route from source to destination.
• Routing Delay: It refers to length of time required to move the packet from source to destination through the internet. Delay depends on many factors i.e bandwidth of intermediate n/w links physical distance to be travelled.
• Bandwidth: It refers to the available traffic or capacity of the link.
• Load: Load can be calculated in different ways i.e CPU utilization and packets process per second.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Routing Table:

​

​

​

​

​

• Mask: This field defines the mask applied for the entry .
• N/w Address: This field shows the name of the interface.
• Next-hop address: This field defines the address of the next half-router to which the packet is delivered.
• Flags: This field defines 5 flags. Flags are ON , OFF switches that signifies either presence or absence. The 5 flags are: UP (U), 2. Gateway (G) 3. Host Specific (H) 4. Added by redirection (D) 5. Modified by re-direction (M).

UP flag : The U flag indicates the router is up and running. If the flag is not present, it means that the router is down. The packet cannot be forwarded and it is discarded.

Gateway flag: The G flag is the destination in another n/w the packet is delivered to the next hop router for delivery.

H flag: The H flag indicates the entry in the n/w address field in a host- specific address

​

​

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

D flag: The D flag indicates the routing information for the destination has been added to the host routing table by a redirection message for ICMP.

M flag:

The M flag indicates the routing information for the destination has been modified by a redirection message from ICMP.

• Reference Count:

This field gives no of users that are using the route at that moment.

• Use:

This field shows a no of packets transmitted through the router for the corresponding destination

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Routing Algorithms:

• The main function of n/w layer is routing the packet from source machine to destination machine. So routing algorithm is a part of n/w layer s/w.
• A path with least cost is referred as best path. Routing algorithm is divided into two groups.
• Non-Adaptive Routing Algorithms
• Adaptive Routing Algorithms
• Non-Adaptive Routing Algorithms:

In this type of algorithm routing decision is not based on measurement and estimation of current n/w traffic & topology. The choice of route is done in advance i.e offline and it is downloaded to the routers. This is called static routing algorithm. In this algorithm the routes are changed slowly. Ex: Optimality principle

shortest path routing: Dijkstra’s algorithm

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

• Adaptive Routing Algorithms:

In this algorithm the routing decision can be changed if there are any changes in the current n/w traffic and topology. This is called dynamic routing algorithm.

Ex:

• Link-state routing
• Distance vector routing
• Hierarchical routing
• Broadcasting routing
• Multicast routing
• Unicast routing

​

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

The Optimality Principle

(a) A network. (b) A sink tree for router B.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

• The purpose of a routing algorithm at a router is to decide which output line an incoming packet should go. The optimal path from a particular router to another may be the least cost path, the least distance path, the least time path, the least hops path or a combination of any of the above.
• The optimality principle says that optimal routes can be made without the knowledge of n/w topology or traffic load.
• All the routing algorithm use a tree called sink tree to determine the optimal routes.
• The sink tree is the set of all optimal routes from all resources to a particular destination with the route.

Dijkstra’s Algorithm:

An algorithm for finding the shortest paths between nodes in a weighted graph

It is a solution to the single-source shortest path problem in graph theory.

It works on both directed and undirected graphs. All edges must have non-negative weights.

Approach: Greedy

Input: Weighted graph G={E,V} and source vertex v € V, such that all edge weights are non-negative.

Output: Lengths of shortest paths from a given source vertex to all other vertices.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Dijkstra’s Algorithm:

• It computes the shortest path b/w a pair of routers or nodes of a graph.
• The algorithm works by labelling each node with its distance from source node to the current node along the best known path.
• Initially all the nodes are labelled with infinity as path are unknown. As the algorithm proceeds and learns the shortest path the labels are changed to reflect the best path.
• Initially all the labels are temporary and made permanent on discovering that the label represent a shortest possible path from source node to current node.
• Dijkstra’s algorithm works only for positive weights.
• Dijkstra’s algorithm is used for both directed and undirected graph.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Shortest Path Algorithm (1)

The first five steps used in computing the shortest path from A to D. The arrows indicate the working node

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Link State Routing

Each router must do the following:

1. Discover its neighbors, learn their network address.
2. Measure the delay or cost to each of its neighbors.
3. Construct a packet telling all it has just learned.
4. Send this packet to all other routers.
5. Compute the shortest path to every other router.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Link State Routing

1. Discover neighbors, learn network addresses.
2. Set distance/cost metric to each neighbor.
3. Construct packet telling all learned.
4. Send packet to, receive packets from other routers.
5. Compute shortest path to every other router.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Building Link State Packets

(a) A network. (b) The link state packets for this network.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Shortest path from A routing table

A->B 4

A->C 6

A->D 9

A->E 5

A->F 10

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Flooding

Definition:

Flooding is a simple computer network routing algorithm in which every incoming packet is sent through every outgoing link except the one it arrived on.

• One major problem of this algorithm is that it generates a large number of duplicate packets on the network.
• One solution is to include a hop counter in the header of each packet.
• Another technique is to keep the track of the packed that have been flooded, to avoid sending them a second time.
• Another solution is to use selective flooding. In selective flooding the routers do not send every incoming packet out on every output line. Instead packet is sent only on those lines which are approximately going in the right direction.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

DISTANCE VECTOR ROUTING

• Each router maintains a routing table, where each node in the network has an entry in the table.
• Each entry contains two parts, the outgoing line for the destination (node) and the distance (time, cost, whatever) to the destination.
• Each router knows the distance to its neighbors
• In a certain period of time, each router sends the table to each of its neighbors.
• When a router receives a table from each of its neighbors, it updates its routing table, determines the new minimum distance and the outgoing link for the destination. �

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Distance Vector Routing

(a) A network. �(b) Input from A, I, H, K, and the new routing table for J.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Advantages and Disadvantages

Advantages:

1. Stable and proven method (distance vector was the original routing algorithm)
2. Easy to implement and administer
3. Bandwidth requirements negligible for a typical LAN environment
4. It is simpler to configure and maintain than Link State

Disadvantages :

1. Large routing tables
2. High convergence time. 
3. High network traffic overhead. 
4. Does not scale

The count-to-infinity problem happens when a router is unable to reach an adjoining network

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Hierarchical Routing

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Hierarchical Routing

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Broadcast Routing

• Sending a packet to many or all the destinations is called as broadcasting. The Following are can be used for broadcasting.�

Method 1:A distinct packet is sent to each destination. This process wastes bandwidth.

Method 2: Flooding

Method 3: Multi dimensional routing

Method 4: Spanning tree

Method 5: Reverse Path Forwarding

​

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Congestion Control Algorithms (1)

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Closed loop techniques�

Congestion control in virtual subnets

• Admission control
• Alternative path
• Agreement negotiation

​

Congestion control in datagram subnets

• Warning bit
• Choke packets
• Hop by Hop Choke packets

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Warning bit

• A special bit in the packet header is set by the router to warn the source when congestion is detected.
• The bit is copied and piggy-backed on the ACK and sent to the sender.
• The sender monitors the number of ACK packets it receives with the warning bit set and adjusts its transmission rate accordingly.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Choke packets

• A more direct way of telling the source to slow down.
• A choke packet is a control packet generated at a congested node and transmitted to restrict traffic flow.
• The source, on receiving the choke packet must reduce its transmission rate by a certain percentage.
• An example of a choke packet is the ICMP Source Quench Packet.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Hop-by Hop Choke Packets

• In this approach, unlike choke packet, reduction of flow starts from intermediate node rather than source node.
• Over long distances or at high speeds choke packets are not very effective.
• A more efficient method is to send to choke packets hop-by-hop.
• This requires each hop to reduce its transmission even before the choke packet arrive at the source

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

A choke packet that affects only the source..

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

A choke packet that affects each hop it passes through.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Load Shedding

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Quality of Service

• Application requirements
• Traffic shaping
• Packet scheduling
• Admission control
• Integrated services
• Differentiated services

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Application Requirements (1)

How stringent the quality-of-service requirements are.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Categories of QoS and Examples

1. Constant bit rate
• Telephony
2. Real-time variable bit rate
• Compressed videoconferencing
3. Non-real-time variable bit rate
• Watching a movie on demand
4. Available bit rate
• File transfer

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Internetworking

• How networks differ
• How networks can be connected
• Tunneling
• Internetwork routing
• Packet fragmentation

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

How Networks Differ

Some of the many ways networks can differ

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

How Networks Can Be Connected

1. A packet crossing different networks.
2. Network and link layer protocol processing.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Tunneling (1)

Tunneling a packet from Paris to London.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Tunneling (2)

Tunneling a car from France to England

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Packet Fragmentation (1)

Packet size issues:

​

1. Hardware
2. Operating system
3. Protocols
4. Compliance with (inter)national standard.
5. Reduce error-induced retransmissions
6. Prevent packet occupying channel too long.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Packet Fragmentation (2)

1. Transparent fragmentation.
2. Nontransparent fragmentation

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Packet Fragmentation (4)

Fragmentation when the elementary data size is 1 byte

(b) Fragments after passing through a network

with maximum packet size of 8 payload bytes plus header.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

The Network Layer Principles (1)

1. Make sure it works
2. Keep it simple
3. Make clear choices
4. Exploit modularity
5. Expect heterogeneity� . . .

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

The Network Layer Principles (2)

. . .

6. Avoid static options and parameters
7. Look for good design (not perfect)
8. Strict sending, tolerant receiving
9. Think about scalability
10. Consider performance and cost

​

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

The Network Layer in the Internet (1)

• The IP Version 4 Protocol
• IP Addresses
• IP Version 6
• Internet Control Protocols
• Label Switching and MPLS
• OSPF—An Interior Gateway Routing Protocol
• BGP—The Exterior Gateway Routing Protocol
• Internet Multicasting
• Mobile IP

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

The Network Layer in the Internet (2)

The Internet is an interconnected collection of many networks.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IP Addresses (2)

Splitting an IP prefix into separate networks with subnetting.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IP Addresses (3)

A set of IP address assignments

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IP Addresses (4)

Aggregation of IP prefixes

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IP Addresses (5)

Longest matching prefix routing at the New York router.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IP Version 6 (2)

IPv6 extension headers

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IP Version 6 (3)

The hop-by-hop extension header for �large datagrams (jumbograms).

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

IP Version 6 (4)

The extension header for routing.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Internet Control Protocols (1)

The principal ICMP message types.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Internet Control Protocols (2)

Two switched Ethernet LANs joined by a router

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Label Switching and MPLS (1)

Transmitting a TCP segment using IP, MPLS, and PPP.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

Label Switching and MPLS (2)

Forwarding an IP packet through an MPLS network

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

OSPF—An Interior Gateway �Routing Protocol (1)

An autonomous system

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

OSPF—An Interior Gateway �Routing Protocol (2)

A graph representation of the previous slide.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

OSPF—An Interior Gateway �Routing Protocol (3)

The relation between ASes, backbones, and areas in OSPF.

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

OSPF—An Interior Gateway �Routing Protocol (4)

The five types of OSPF messages

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

BGP—The Exterior Gateway �Routing Protocol (1)

Examples of routing constraints:

​

1. No commercial traffic for educat. network
2. Never put Iraq on route starting at Pentagon
3. Choose cheaper network
4. Choose better performing network
5. Don’t go from Apple to Google to Apple

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

BGP—The Exterior Gateway �Routing Protocol (2)

Routing policies between four Autonomous Systems

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​

BGP—The Exterior Gateway �Routing Protocol (3)

Propagation of BGP route advertisements

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011

​