UNIT-III
Network Layer Design Issues
[Link]-and-forward packet switching
[Link] provided to transport layer
[Link] of connectionless service
[Link] of connection-oriented service
[Link] of virtual-circuit and datagram networks
[Link]-and-forward packet switching
A host with a packet to send transmits it to the nearest router, either on its own LAN or over a point-to-point link to the ISP.
The packet is stored there until it has fully arrived and the link has finished its processing by verifying the checksum. Then it
is forwarded to the next router along the path until it reaches the destination host, where it is delivered. This mechanism is
store-and-forward packet switching
[Link] provided to transport layer
The network layer provides services to the transport layer at the network layer/transport layer interface. The services need to
be carefully designed with the following goals in mind:
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
– even across LANs and WANs
[Link] of connectionless service
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.
A’s table (initially) A’s table (later) C’s Table E’s Table
Let us assume for this example that the message is four times longer than the maximum packet size, so the network
layer has to break it into four packets, 1, 2, 3, and 4, and send each of them in turn to router A.
Every router has an internal table telling it where to send packets for each of the possible destinations. Each table entry
is a pair(destination and the outgoing line). Only directly connected lines can be used.
A’s initial routing table is shown in the figure under the label ‘‘initially.’’
At A, packets 1, 2, and 3 are stored briefly, having arrived on the incoming link. Then each packet is forwarded
according to A’s table, onto the outgoing link to C within a new frame. Packet 1 is then forwarded to E and then to F.
However, something different happens to packet 4. When it gets to A it is sent to router B, even though it is also destined
for F. For some reason (traffic jam along ACE path), A decided to send packet 4 via a different route than that of the
first three packets. Router A updated its routing table, as shown under the label ‘‘later.’’
The algorithm that manages the tables and makes the routing decisions is called the routing algorithm.
[Link] of connection-oriented service
A’s table C’s Table E’s Table
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), and the network
is called a virtual-circuit network
When a connection is established, a route from the source machine to the destination machine is chosen as part
of the connection setup and stored in tables inside the routers. That route is used for all traffic flowing over the
connection, exactly the same way that the telephone system works. When the connection is released, the virtual
circuit is also terminated. With connection-oriented service, each packet carries an identifier telling which virtual
circuit it belongs to.
As an example, consider the situation shown in Figure. Here, host H1 has established connection 1 with host H2.
This connection is remembered as the first entry in each of the routing tables. The first line of A’s table says that
if a packet bearing connection identifier 1 comes in from H1, it is to be sent to router C and given connection
identifier 1. Similarly, the first entry at C routes the packet to E, also with connection identifier 1.
Now let us consider what happens if H3 also wants to establish a connection to H2. It chooses connection identifier
1 (because it is initiating the connection and this is its only connection) and tells the network to establish the
virtual circui
This leads to the second row in the tables. Note that we have a conflict here because although A can easily distinguish
connection 1 packets from H1 from connection 1 packets from H3, C cannot do this. For this reason, A assigns a
different connection identifier to the outgoing traffic for the second connection. Avoiding conflicts of this kind is why
routers need the ability to replace connection identifiers in outgoing packets.
In some contexts, this process is called label switching. An example of a connection-oriented network service is MPLS
(Multi-Protocol Label Switching).
Routing Algorithms
Different Routing Algorithms
Shortest path algorithm
Flooding
Distance vector routing
Hierarchical Routing
Shortest Path Routing (Dijkstra’s)
[Link] with the local node (router) as the root of the tree. Assign a The idea is to build a graph of the subnet, with
each node of the graph representing a router and each arc of the graph representing a communication line or link.
To choose a route between a given pair of routers, the algorithm just finds the shortest path between them on the graph
cost of 0 to this node and make it the first permanent node.
[Link] each neighbor of the node that was the last permanent node.
[Link] a cumulative cost to each node and make it tentative
4. Among the list of tentative nodes
a. Find the node with the smallest cost and make it Permanent
b. If a node can be reached from more than one route then select the route with the shortest cumulative cost.
[Link] steps 2 to 4 until every node becomes permanent
Flooding
• Another static algorithm is flooding, in which 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, which is decremented at
each hop, with the packet being discarded when the counter reaches zero. Ideally, the hop counter should be
initialized to the length of the path from source to destination.
• A variation of flooding that is slightly more practical is selective flooding. In this algorithm the routers do
not send every incoming packet out on every line, only on those lines that are going approximately in the right
direction.
• Flooding is not practical in most applications.
Intra- and Inter domain Routing
An autonomous system (AS) is a group of networks and routers under the authority of a single administration.
Routing inside an autonomous system is referred to as intra domain routing. (DISTANCE VECTOR, LINK
STATE
Routing between autonomous systems is referred to as inter domain routing. (PATH VECTOR) Each
autonomous system can choose one or more intra domain routing protocols to handle routing inside the autonomous
system. However, only one inter domain routing protocol handles routing between autonomous systems.
Hierarchical Routing
As networks grow in size, the router routing tables grow proportionally. Not only is router memory consumed by ever-
increasing tables, but more CPU time is needed to scan them and more bandwidth is needed to send status reports
about them.
At a certain point, the network may grow to the point where it is no longer feasible for every router to have an entry
for every other router, so the routing will have to be done hierarchically, as it is in the telephone network.
When hierarchical routing is used, the routers are divided into what we will call regions. Each router knows all the
details about how to route packets to destinations within its own region but knows nothing about the internal structure
of other 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, until we run out of names for aggregations
When a single network becomes very large, an interesting question is ‘‘how many levels
should the hierarchy have?’’
For example, consider a network with 720 routers. If there is no hierarchy, each router needs 720 routing table
entries.
If the network is partitioned into 24 regions of 30 routers each, each router needs 30 local entries plus 23 remote
entries for a total of 53 entries.
If a three-level hierarchy is chosen, with 8 clusters each containing 9 regions of 10 routers,
each router needs 10 entries for local routers, 8 entries for routing to other regions within
its own cluster, and 7 entries for distant clusters, for a total of 25 entries
Kamoun and Kleinrock (1979) discovered that the optimal number of levels for an N router
network is ln N, requiring a total of e ln N entries per router
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. Since
congestion occurs within the network, it is the network layer that directly experiences it
and must ultimately determine what to do with the excess packets.
However, the most effective way to control congestion is to reduce the load that the
transport layer is placing on the network. This requires the network and transport layers to
work together. In this chapter we will look at the network aspects of congestion.
When too much traffic is offered, congestion sets in and performance degrades sharply
Above Figure depicts the onset of congestion. When the number of packets hosts send into
the network is well within its carrying capacity, the number delivered is proportional to the
number sent. If twice as many are sent, twice as many are delivered. However, as the offered
load approaches the carrying capacity, bursts of traffic occasionally fill up the buffers inside
routers and some packets are lost. These lost packets consume some of the capacity, so the
number of delivered packets falls below the ideal curve. The network is now congested.
Unless the network is well designed, it may experience a congestion collapse
Traffic Shaping
1. Another method of congestion control is to “shape” the traffic before it enters the
network.
2. Traffic shaping controls the rate at which packets are sent (not just how many).
Used in ATM and Integrated Services networks.
3. At connection set-up time, the sender and carrier negotiate a traffic pattern (shape).
Two traffic shaping algorithms are:
Leaky bucket
Token bucket
The Leaky Bucket Algorithm used to control rate in a network. It is implemented as a
single- server queue with constant service time. If the bucket (buffer) overflows then
packets are discarded.
(a) A leaky bucket with water (b) a leaky bucket with packets
[Link] leaky bucket enforces a constant output rate (average rate) regardless of the
burstiness of the input. Does nothing when input is idle.
[Link] host injects one packet per clock tick onto the network. This results in a uniform flow
of packets, smoothing out bursts and reducing congestion.
[Link] packets are the same size (as in ATM cells), the one packet per tick is okay. For
variable length packets though, it is better to allow a fixed number of bytes per tick. E.g.
1024 bytes per tick will allow one 1024-byte packet or two 512-byte packets or four 256-
byte packets on 1 tick
Token Bucket Algorithm
[Link] contrast to the LB, the Token Bucket Algorithm, allows the output rate
to vary, depending on the size of the burst.
[Link] the TB algorithm, the bucket holds tokens. To transmit a packet, the host must
capture and destroy one token.
[Link] are generated by a clock at the rate of one token every t sec.
[Link] hosts can capture and save up tokens (up to the max. size of the bucket) in
order to send larger bursts later.
Leaky Bucket vs. Token Bucket
1. LB discards packets; TB does not. TB discards tokens.
2. With TB, a packet can only be transmitted if there are enough tokens to cover its
length in bytes.
3. LB sends packets at an average rate. TB allows for large bursts to be sent faster
by speeding up the output.
4. TB allows saving up tokens (permissions) to send large bursts. LB does not allow
saving.