UNIT-III : THE NETWORK LAYER��

• Network layer design issues
• Routing algorithms
• Congestion control algorithms
• Internetworking
• The network layer in the internet (IPv4 and IPv6)
• Quality of Service

• Network layer design issues

Network layer design issues

These issues include the service provided to the transport layer

1. Store-and-Forward Packet Switching
2. Services Provided to the Transport Layer
3. Implementation of Connectionless Service
4. Implementation of Connection-Oriented Service
5. Comparison of Virtual-Circuit and Datagram Networks

1.Store-and-Forward Packet Switching �

The major components of the network are the ISP’s equipment (routers connected by transmission lines), shown inside the shaded oval, and the customers’ equipment, shown outside the oval.

​

​

​

​

​

​

A host with a packet to send transmits it to the nearest router.

The packet is stored there until it has fully arrived. Then it is forwarded to the next router along the path until it reaches the destination host, where it is delivered.

2.Services Provided to the Transport Layer ��

The network layer provides services to the transport layer at the network layer/transport layer interface.

1.The services should be independent of the router technology.

2.The transport layer should be shielded from the number, type, and topology of the routers present.

3. The network addresses made available to the transport layer should use a uniform numbering plan, even across LANs and WANs.

2 Types of services Provided by Network Layer

Connectionless service

Connection-oriented services

​

3.Implementation of Connectionless Service ���

Two different organizations are possible

If connectionless service is offered, packets are injected into the network individually and routed independently of each other. No advance setup is needed. In this context, the packets are frequently called datagrams (in analogy with telegrams) and the network is called a datagram network.

If connection-oriented service is used, a path from the source router all the way to the destination router must be established before any data packets can be sent. This connection is called a VC (virtual circuit), in analogy with the physical circuits set up by the telephone system, and the network is called a virtual-circuit network.

3.Implementation of Connectionless Service ���

The algorithm that manages the tables and makes the routing decisions is called the routing algorithm

4.Implementation of Connection-Oriented Service��

For connection-oriented service, we need a virtual-circuit network

​

5.Comparison of Virtual-Circuit and Datagram Networks ���

Routing algorithms

Routing algorithms����

• The algorithm that manages the tables and makes the routing decisions is called the routing algorithm
• The routing algorithm is that part of the network layer software responsible for deciding which output line an incoming packet should be transmitted on.
• Two types of Routing Algorithms

1.Nonadaptive algorithms

2. Adaptive algorithms

Routing algorithms����

• Nonadaptive algorithms do not base their routing decisions on any measurements or estimates of the current topology and traffic. Instead, the choice of the route is computed in advance, off-line, and downloaded to the routers when the network is booted. This procedure is sometimes called static routing.
• Adaptive algorithms, in contrast, change their routing decisions to reflect changes in the topology, and sometimes changes in the traffic as well. These dynamic routing algorithms differ in where they get their information, when they change the routes, and what metric is used for optimization (e.g., distance, number of hops, or estimated transit time).

Routing algorithms����

1. The optimality principle
2. The Shortest Path Algorithm
3. Flooding
4. Distance Vector Routing
5. Link State Routing
6. Hierarchical Routing
7. Broadcast Routing
8. Multicast Routing

​

​

​

​

​

1.The optimality principle����

1. The set of optimal routes from all sources to a given destination form a tree rooted at the destination. Such a tree is called a sink tree
2. The goal of all routing algorithms is to discover and use the sink trees for all routers

2 Shortest Path Algorithm����

• This algorithm is called Dijkstra’s algorithm
• It finds the shortest paths between a source and all destinations in the network.
• Each node is labeled (in parentheses) with its distance from the source node along the best known path.
• The distances must be non-negative,
• Initially, no paths are known, so all nodes are labeled with infinity.
• As the algorithm proceeds and paths are found, the labels may change, reflecting better paths.
• Initially, all labels are tentative.
• When it is discovered that a label represents the shortest possible path from the source to that node, it is made permanent and never changed thereafter.

2 Shortest Path Algorithm����

3 Flooding���

• Every incoming packet is sent out on every outgoing line except the one it arrived on
• Flooding obviously generates vast numbers of duplicate packets, in fact, an infinite number unless some measures are taken to damp the process.
• One such measure is to have a hop counter contained in the header of each packet that is decremented at each hop, with the packet being discarded when the counter reaches zero.
• If the sender does not know how long the path is, it can initialize the counter to the worst case, namely, the full diameter of the network.

4 Distance Vector Routing

• The distance vector routing algorithm is sometimes called the distributed Bellman-Ford routing algorithm
• A distance vector routing algorithm operates by having each router maintain a table
• These tables are updated by exchanging information with the neighbors.
• Each entry in a router has two parts: the preferred outgoing line to use for that destination and an estimate of the distance to that destination.

4 Distance Vector Routing

4 Distance Vector Routing

The Count-to-Infinity Problem

• Drawback: Although it converges to the correct answer, it may do so slowly. In particular, it reacts rapidly to good news, but leisurely to bad news.

​

5 Link State Routing

• Link State Routing replaced the Distance vector routing which was used in the ARPANET until 1979
• Variants of link state routing called IS-IS and OSPF are the routing algorithms that are most widely used inside large networks and the Internet today.
• The 5 steps in Link State Routing
• Discover its neighbors and learn their network addresses.
• Set the distance or cost metric to each of its neighbors.
• Construct a packet telling all it has just learned.
• Send this packet to and receive packets from all other routers.
• Compute the shortest path to every other router.

5 Link State Routing

1.Learning about the Neighbors

• When a router is booted, its first task is to learn who its neighbors are.
• 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.

5 Link State Routing

2.Setting Link Costs

• The link state routing algorithm requires each link to have a distance or cost metric for finding shortest paths.
• The cost to reach neighbors can be set automatically, or configured by the network operator
• The most direct way to determine the delay is to send over the line a special ECHO packet 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.

5 Link State Routing

3.Building Link State Packets

• Once the information needed for the exchange has been collected, the next step is for each router to build a packet containing all the data.
• The packet starts with the identity of the sender, followed by a sequence number and age and a list of neighbors. The cost to each neighbor is also given.

5 Link State Routing

4.Distributing the Link State Packets

• Uses flooding to distribute the link state packets to all routers. To keep the flood in check, each packet contains a sequence number that is incremented for each new packet sent.
• 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.
• This algorithm has a few problems: if the sequence numbers wrap around, if a router ever crashes, it will lose track of its sequence number.
• The solution to all these problems is to include the age of each packet after the sequence number and decrement it once per second. When the age hits zero, the information from that router is discarded

5 Link State Routing

4.Distributing the Link State Packets

5 Link State Routing

5. Computing the New Routes

• Now Dijkstra’s algorithm can be run locally to construct the shortest paths to all possible destinations.
• The results of this algorithm tell the router which link to use to reach each destination.
• This information is installed in the routing tables, and normal operation is resumed.

​

• Compared to distance vector routing, link state routing requires more memory and computation.
• Link state routing is widely used in actual networks

6 Hierarchical Routing

• When hierarchical routing is used, the routers are divided into what we will call regions
• For huge networks, a two-level hierarchy may be insufficient;
• It may be necessary to group the regions into clusters, the clusters into zones, the zones into groups, and so on,

6 Hierarchical Routing

7 Broadcast Routing�

• Sending a packet to all destinations simultaneously is called broadcasting.
• Multidestination routing: Each packet contains either a list of destinations or a bit map indicating the desired destinations. When a packet arrives at a router, the router checks all the destinations to determine the set of output lines that will be needed.
• The router generates a new copy of the packet for each output line to be used and includes in each packet only those destinations that are to use the line.
• After a sufficient number of hops, each packet will carry only one destination like a normal packet.

​

7 Broadcast Routing�

• Another option is to use flooding
• Reverse path forwarding: When a broadcast packet arrives at a router, the router checks to see if the packet arrived on the link that is normally used for sending packets toward the source of the broadcast.
• If so, there is an excellent chance that the broadcast packet itself followed the best route from the router and is therefore the first copy to arrive at the router. This being the case, the router forwards copies of it onto all links except the one it arrived on.
• If,however, the broadcast packet arrived on a link other than the preferred one for reaching the source, the packet is discarded as a likely duplicate.

7 Broadcast Routing�

8 Multicast Routing�

• Sending a message to a group is called multicasting, and the routing algorithm used is called multicast routing.
• All multicasting schemes require some way to create and destroy groups and to identify which routers are members of a group.
• MOSPF (Multicast OSPF) is an example of a link state protocol that works for multicast routing
• DVMRP (Distance Vector Multicast Routing Protocol) is an example of a multicast routing protocol

8 Multicast Routing�

UNIT-III : THE NETWORK LAYER��

Congestion control algorithms

CONGESTION CONTROL ALGORITHMS�

• Too many packets present in (a part of) the network causes packet delay and loss that degrades performance. This situation is called congestion.
• The network and transport layers share the responsibility for handling congestion

Approaches to Congestion Control

• The presence of congestion means that the load is (temporarily) greater than the resources (in a part of the network) can handle.
• Two solutions : increase the resources or decrease the load.

Approaches to Congestion Control

1 Network provisioning

• The most basic way to avoid congestion is to build a network that is well matched to the traffic that it carries.
• If there is a low-bandwidth link on the path along which most traffic is directed, congestion is likely.
• Sometimes resources can be added dynamically when there is serious congestion
• More often, links and routers that are regularly heavily utilized are upgraded at the earliest opportunity.
• This is called provisioning and happens on a time scale of months, driven by long-term traffic trends.

​

Approaches to Congestion Control

2 Traffic-aware routing.

​

• To make the most of the existing network capacity, routes can be tailored to traffic patterns that change during the day as network users wake and sleep in different time zones.
• For example, routes may be changed to shift traffic away from heavily used paths by changing the shortest path weights.
• This is called traffic-aware routing.
• Splitting traffic across multiple paths is also helpful.

Approaches to Congestion Control

2 Traffic-Aware routing-Problems

• In the Internet routing protocols do not generally adjust their routes depending on the load. Instead, adjustments are made outside the routing protocol by slowly changing its inputs. This is called traffic engineering.

​

Approaches to Congestion Control

3 Admission Control

​

• Sometimes it is not possible to increase capacity.
• The only way then to beat back the congestion is to decrease the load.
• In a virtual-circuit network, new connections can be refused if they would cause the network to become congested.
• The idea is simple: do not set up a new virtual circuit unless the network can carry the added traffic without becoming congested. Thus, attempts to set up a virtual circuit may fail.
• This is called admission control.

Approaches to Congestion Control

3 Admission Control

​

Approaches to Congestion Control

4 Traffic Throttling

• In the Internet and many other computer networks, senders adjust their transmissions to send as much traffic as the network can readily deliver.
• In this setting,the network aims to operate just before the onset of congestion.
• When congestion is imminent, it must tell the senders to throttle back their transmissions and slow down.

Approaches to Congestion Control

4 Traffic Throttling- Choke Packet

• The most direct way to notify a sender of congestion is to tell it directly.
• In this approach, the router selects a congested packet and sends a choke packet back to the source host, giving it the destination found in the packet.

Approaches to Congestion Control- 4 Traffic Throttling- Choke Packet �

Approaches to Congestion Control

4 Traffic Throttling-

ECN (Explicit Congestion Notification)

• Instead of generating additional packets to warn of congestion, a router can tag any packet it forwards to signal that it is experiencing congestion.

Approaches to Congestion Control

4 Traffic Throttling

• Two bits in the IP packet header are used to record whether the packet has experienced congestion.

Approaches to Congestion Control

4 Traffic Throttling

Hop-by-Hop Backpressure

• At high speeds or over long distances, many new packets may be transmitted after congestion has been signaled because of the delay before the signal takes effect.

Approaches to Congestion Control

5 Load Shedding

• When all else fails, the network is forced to discard packets that it cannot deliver.
• The general name for this is load shedding.
• The key question for a router drowning in packets is which packets to drop.
• The preferred choice may depend on the type of applications that use the network.
• For a file transfer, an old packet is worth more than a new one. This is because dropping packet 6 and keeping packets 7 through 10, for example, will only force the receiver to do more work to buffer data that it cannot yet use.

Approaches to Congestion Control

5 Load Shedding

• In contrast, for real-time media, a new packet is worth more than an old one
• More intelligent load shedding requires cooperation from the senders.

Random Early Detection

• By having routers drop packets early, before the situation has become hopeless, there is time for the source to take action before it is too late. A popular algorithm for doing this is called RED (Random Early Detection)