Unit IV

Network Layer: Design Issues – Routing Algorithms.

Transport Layer: Transport Services – Elements of Transport Protocols.

NETWORK LAYER
The network layer is concerned with getting packets from the source all the way to the
destination. Getting to the destination may require making many hops at intermediate routers
along the way. The main function of the network layer is routing packets from the source
machine to the destination machine..

NETWORK LAYER DESIGN ISSUES

Store-and-Forward Packet Switching

The major components of the system are the carrier's equipment (routers connected by
transmission lines), shown inside the shaded oval, and the customers' equipment, shown
outside the oval. Host H1 is directly connected to one of the carrier's routers, A, by a leased
line. In contrast, H2 is on a LAN with a router, F, owned and operated by the customer.

Figure . The environment of the network layer protocols.

This equipment is used as follows. 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 carrier. The packet is stored
there until it has fully arrived so the checksum can be verified. 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.
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.

Implementation of Connectionless Service

If connectionless service is offered, packets are injected into the subnet 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 subnet is called a
datagram subnet. If connection-oriented service is used, a path from the source router 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 subnet is called a virtual-circuit subnet.

Figure . Routing within a datagram subnet.

Implementation of Connection-Oriented Service

For connection-oriented service, we need a virtual-circuit subnet. Let us see how that works.
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.

Figure . Routing within a virtual-circuit subnet.

 *******************************************

ROUTING ALGORITHMS
The main function of the network layer is routing packets from the source machine to the
destination machine.The routing algorithm is that part of the network layer software
responsible for deciding which output line an incoming packet should be transmitted on.

Shortest Path Routing

This technique is widely used in many forms because it is simple and easy to understand.
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 (often called a link). To choose
a route between a given pair of routers, the algorithm just finds the shortest path between
them on the graph.

Figure . The first five steps used in computing the shortest path from A to D. The arrows
indicate the working node.
Several algorithms for computing the shortest path between two nodes of a graph are known.
This one is due to Dijkstra (1959). Each node is labeled (in parentheses) with its distance
from the source node along the best known path. 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.
Flooding
It is a static algorithm,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,
An alternative technique for damming the flood is to keep track of which packets have been
flooded, to avoid sending them out a second time. To achieve this goal is to have the source
router put a sequence number in each packet it receives from its hosts.
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.

Distance Vector Routing

It is the dynamic routing algorithm. Here, each router maintain a table (i.e, a vector) giving
the best known distance to each destination and which line to use to get there. These tables
are updated by exchanging information with the neighbors.
The distance vector routing algorithm is sometimes called by other names, most commonly
the distributed Bellman-Ford routing algorithm and the Ford-Fulkerson algorithm. It was
the original ARPANET routing algorithm and was also used in the Internet under the name
RIP.
In distance vector routing, each router maintains a routing table indexed by, and containing
one entry for, each router in the subnet. This entry contains two parts: the preferred outgoing
line to use for that destination and an estimate of the time or distance to that destination. The
metric used might be number of hops, time delay in milliseconds, total number of packets
queued along the path, or something similar.

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

Hierarchical Routing
As networks grow in size, the router routing tables grow proportionally. So router memory
increase and more CPU time is needed to scan them and more bandwidth is needed to send
status reports about them.
When hierarchical routing is used, the routers are divided into regions, with each router
knowing all the details about how to route packets to destinations within its own region, but
knowing nothing about the internal structure of other regions.
Figure: Hierarchical routing.

Broadcast Routing
In some applications, hosts need to send messages to many or all other hosts. For example, a
service distributing weather reports, stock market updates, or live radio programs might work
best by broadcasting to all machines and letting those that are interested read the data.
Sending a packet to all destinations simultaneously is called broadcasting. Several methods
are used.
One broadcasting method that requires no special features from the subnet is for the source to
simply send a distinct packet to each destination. Flooding is another obvious method. A third
algorithm is multidestination routing. If this method is used, 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. A fourth broadcast algorithm makes explicit use of the sink tree for the router
initiating the broadcast—or any other convenient spanning tree for that matter. A spanning
tree is a subset of the subnet that includes all the routers but contains no loops.
Our last broadcast algorithm is called reverse path forwarding, is remarkably simple once it
has been pointed out. When a broadcast packet arrives at a router, the router checks to see if
the packet arrived on the line that is normally used for sending packets to 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 lines except the one it arrived on. If, however, the
broadcast packet arrived on a line other than the preferred one for reaching the source, the
packet is discarded as a likely duplicate.

Multicast Routing
Sending a message to such a group is called multicasting, and its routing algorithm is called
multicast routing.
Multicasting requires group management. Some way is needed to create and destroy groups,
and to allow processes to join and leave groups. To do multicast routing, each router
computes a spanning tree covering all other routers.

Figure . (a) A network. (b) A spanning tree for the leftmost router. (c) A multicast tree for
group 1. (d) A multicast tree for group 2.

********************************
TRANSPORT LAYER

The transport layer is not just another layer. It is the heart of the whole protocol hierarchy.
Its task is to provide reliable, cost-effective data transport from the source machine to the
destination machine, independently of the physical network or networks currently in use.

Services Provided to the Upper Layers

The ultimate goal of the transport layer is to provide efficient, reliable, and cost-effective
service to its users, normally processes in the application layer. To achieve this goal, the
transport layer makes use of the services provided by the network layer. The hardware
and/or software within the transport layer that does the work is called the transport entity.
The transport entity can be located in the operating system kernel, in a separate user
process, in a library package bound into network applications, or conceivably on the
network interface card.

Figure:The network, transport, and application layers.

 Just as there are two types of network service, connection-oriented and connectionless,
there are also two types of transport service. The connection-oriented transport service is
similar to the connection-oriented network service in many ways. In both cases,
connections have three phases: establishment, data transfer, and release. Addressing and
flow control are also similar in both layers. Furthermore, the connectionless transport
service is also very similar to the connectionless network service.
Transport Service Primitives
The transport service is similar to the network service, but there are also some important
differences. The main difference is that the network service is intended to model the
service offered by real networks, warts and all. Real networks can lose packets, so the
network service is generally unreliable.
The (connection-oriented) transport service, in contrast, is reliable. Of course, real
networks are not error-free, but that is precisely the purpose of the transport layer—to
provide a reliable service on top of an unreliable network.
.

Figure . The primitives for a simple transport service.

Figure. Nesting of TPDUs, packets, and

frames.
Getting back to our client-server example, the client's CONNECT call causes a
CONNECTION REQUEST TPDU to be sent to the server. When it arrives, the transport
entity checks to see that the server is blocked on a LISTEN (i.e., is interested in handling
requests). It then unblocks the server and sends a CONNECTION ACCEPTED TPDU
back to the client. When this TPDU arrives, the client is unblocked and the connection is
established.
Data can now be exchanged using the SEND and RECEIVE primitives. In the simplest
form, either party can do a (blocking) RECEIVE to wait for the other party to do a SEND.
When the TPDU arrives, the receiver is unblocked. It can then process the TPDU and send
a reply. As long as both sides can keep track of whose turn it is to send, this scheme works
fine.

************************

ELEMENTS OF TRANSPORT PROTOCOLS

The transport service is implemented by a transport protocol used between the two
transport entities
Figure. (a) Environment of the data link layer. (b) Environment of the transport layer.

Addressing
When an application (e.g., a user) process wishes to set up a connection to a remote
application process, it must specify which one to connect to. (Connectionless transport has
the same problem: To whom should each message be sent?) The method normally used is
to define transport addresses to which processes can listen for connection requests. In the
Internet, these end points are called ports. In ATM networks, they are called AAL-SAPs.
We will use the generic term TSAP, (Transport Service Access Point). The analogous
end points in the network layer (i.e., network layer addresses) are then called NSAPs. IP
addresses are examples of NSAPs.
A possible scenario for a transport connection is as follows.
 1. A time of day server process on host 2 attaches itself to TSAP 1522 to wait for an
incoming call. How a process attaches itself to a TSAP is outside the networking
model and depends entirely on the local operating system. A call such as our
LISTEN might be used, for example.
2. An application process on host 1 wants to find out the time-of-day, so it issues a
CONNECT request specifying TSAP 1208 as the source and TSAP 1522 as the
destination. This action ultimately results in a transport connection being
established between the application process on host 1 and server 1 on host 2.
3. The application process then sends over a request for the time.
4. The time server process responds with the current time.
5. The transport connection is then released.

Flow Control and Buffering

In the data link layer, the sending side must buffer outgoing frames because they might
have to be retransmitted. If the subnet provides datagram service, the sending transport
entity must also buffer, and for the same reason. If the receiver knows that the sender
buffers all TPDUs until they are acknowledged, the receiver may or may not dedicate
specific buffers to specific connections, as it sees fit. The receiver may, for example,
maintain a single buffer pool shared by all connections. When a TPDU comes in, an
attempt is made to dynamically acquire a new buffer. If one is available, the TPDU is
accepted; otherwise, it is discarded. Since the sender is prepared to retransmit TPDUs lost
by the subnet, no harm is done by having the receiver drop TPDUs, although some
resources are wasted. The sender just keeps trying until it gets an acknowledgement.

Figure: (a) Chained fixed-size buffers. (b) Chained variable-sized buffers. (c) One large
circular buffer per connection.

Multiplexing
Multiplexing several conversations onto connections, virtual circuits, and physical links
plays a role in several layers of the network architecture. In the transport layer the need for
multiplexing can arise in a number of ways. For example, if only one network address is
available on a host, all transport connections on that machine have to use it. When a TPDU
comes in, some way is needed to tell which process to give it to. This situation, called
upward multiplexing.

Figure . (a) Upward multiplexing. (b) Downward

multiplexing.

Multiplexing can also be useful in the transport layer for another reason. Suppose, for
example, that a subnet uses virtual circuits internally and imposes a maximum data rate on
each one. If a user needs more bandwidth than one virtual circuit can provide, a way out is
to open multiple
network connections and distribute the traffic among them on a round-robin basis. This
modus operandi is called downward multiplexing.

Crash Recovery
If hosts and routers are subject to crashes, recovery from these crashes becomes an issue. If
the transport entity is entirely within the hosts, recovery from network and router crashes is
straightforward. If the network layer provides datagram service, the transport entities
expect lost TPDUs all the time and know how to cope with them. If the network layer
provides connection- oriented service, then loss of a virtual circuit is handled by
establishing a new one and then probing the remote transport entity to ask it which TPDUs
it has received and which ones it has not received. The latter ones can be retransmitted.
A more troublesome problem is how to recover from host crashes. In particular, it may be
desirable for clients to be able to continue working when servers crash and then quickly
reboot. To illustrate the difficulty, let us assume that one host, the client, is sending a long
file to another host, the file server, using a simple stop-and-wait protocol. The transport
layer on the server simply passes the incoming TPDUs to the transport user, one by one.
Partway through the transmission, the server crashes. When it comes back up, its tables are
reinitialized, so it no longer knows precisely where it was.
In an attempt to recover its previous status, the server might send a broadcast TPDU to all
other hosts, announcing that it had just crashed and requesting that its clients inform it of
the status of all open connections. Each client can be in one of two states: one TPDU
outstanding, S1, or no TPDUs outstanding, S0. Based on only this state information, the
client must decide whether to retransmit the most recent TPDU.

*****************************************