Transcript Network Layer - King Fahd University of Petroleum and Minerals

Network Standards
Khaled M. Elleithy, Ph.D.
[email protected]
Department of Computer Engineering
King Fahd University of Petroleum and
Minerals
Dhahran, Saudi Arabia
Topics Covered in this Session


Why Communication Standards?
The OSI Reference Model
21December, 1997
COE Department * Dr. Elleithy
2
Why Communications
Standards?



Incompatible products from different
manufacturers
The need to allow different manufacturers
products to communicate
The need to provide a framework for networks
to be acceptable from all manufacturers
21December, 1997
COE Department * Dr. Elleithy
3
Layered Architecture



A layer is corresponding to a different
abstraction level
Each layer should perform a well defined
function
Layers should be chosen to minimize
information exchange between different layers
21December, 1997
COE Department * Dr. Elleithy
4
OSI Reference Model







Application layer
Presentation layer
Session layer
Transport layer
Network layer
Data link layer
Physical layer
21December, 1997
COE Department * Dr. Elleithy
5
OSI Reference Model
21December, 1997
COE Department * Dr. Elleithy
6
Physical Layer


The Physical Layer is simply responsible for sending bits
from one computer to the another. The Physical Layer is
not concerned with the meaning of the bits.
This level defines physical and electrical details, such as
what will represent 1 or 0, how many pins a network
connector will have, how data will be synchronized, and
when the network adapter may or may not transmit the
data.
21December, 1997
COE Department * Dr. Elleithy
7
Physical Layer

Couplers, cables and cabling, connectors,
multiplexers, transmitters, receivers and
transceivers are devices associated with
the physical layer.
21December, 1997
COE Department * Dr. Elleithy
8
Physical Layer

The following items are addressed at the
physical layer
» Network connection types, including
multipoint and point-to-point connections.
» Physical topologies, which are physical
layouts of networks, such as bus, star or
ring
21December, 1997
COE Department * Dr. Elleithy
9
Physical Layer
» Analog and digital signaling, which include
several methods for encoding data in
analog and digital signals.
» Bit synchronization, which deals with
synchronization between sender and
receiver.
» Baseband and Broadband transmissions,
which are different methods for using media
bandwidth.
21December, 1997
COE Department * Dr. Elleithy
10
Data Link Layer


The data link layer provides for the flow of data
over a single link from one device to another. It
accepts packets from the network layer and
packages the information into data units called
frames to be presented to the physical layer for
transmission.
A Cyclic Redundancy Check (CRC) added to the
data frame can detect damaged frames, and the
data link layer in the receiving computer can
request that the information be present. The data
link layer can also detect when frames are lost
and request that those frames be sent again.
21December, 1997
COE Department * Dr. Elleithy
11
Data Link Layer

A data frame that’s all packaged and ready to
go follows this format:
»
»
»
»
The start indicator
The source address
The destination address
The control portion: like special handling
instructions
» The actual data
» The error control segment or the CRC
21December, 1997
COE Department * Dr. Elleithy
12
Data Link Layer

Bridges, intelligent hubs, and network
interface cards are devices typically
associated with the data link layer.

Two sub-layers make up the data link layer:
» Media Access Control (MAC)
» Logical Link Control (LLC)
21December, 1997
COE Department * Dr. Elleithy
13
Network Layer

The network layer makes routing decisions and forwards
packets for devices that are farther away than a single link.
(A link connects two network devices and is implemented
by the data link layer. Two devices connected by a link
communicate directly with each other and not through a
third device.) In larger networks there may be intermediate
systems between any two end systems, and the network
layer makes it possible for the transport layer and layers
above it to send packets without being concerned about
whether the end system is immediately adjacent or several
hops away.
21December, 1997
COE Department * Dr. Elleithy
14
Network Layer



The network layer translates logical network addresses
into physical machine addresses (the numbers used as
destination IDs in the physical network cards). This layer
also determines the quality of service (such as the priority
of the message) and the route a message will take if there
are several ways a message can get to its destination.
It also may break large packets into smaller chunks if the
packet is larger than the largest data frame the data link
layer will accept. The network reassembles the chunks into
packets at the receiving end.
Routers and gateways operate in the network layer.
21December, 1997
COE Department * Dr. Elleithy
15
Network Layer


The network layer is concerned with
controlling the operation of the subnet. A key
design issue is determining how packets are
routed from source to destination.
If too many packets are present in the subnet
at the same time, they will get in each other’s
way, forming bottlenecks. The control of such
congestion also belongs to the network layer.
21December, 1997
COE Department * Dr. Elleithy
16
Network Layer

The network layer serves to support
communications between logically separate
networks. This layer is concerned with the
following.
» Addressing, including logical network
addresses and service addresses
» Circuit, message, and packet switching
» Route discovery and route selection
» Connection services, including network layer
flow control, network layer error control, and
packet sequence control.
» Gateway services.
21December, 1997
COE Department * Dr. Elleithy
17
Transport Layer

The transport layer ensures that packets are
delivered error free, in sequence, and with no
losses or duplications. The transport layer
breaks large messages from the session layer
into packets to be sent to the destination
computer and reassembles packets into
messages to be presented to the session
layer in the destination layer.
21December, 1997
COE Department * Dr. Elleithy
18
Transport Layer



The transport layer typically sends an
acknowledgment to the originator for
messages received.
The transport layer also determines what type
of service to provide the session layer, and
ultimately, the users of the network.
The transport and network layers deal with the
logical transmission of data.
21December, 1997
COE Department * Dr. Elleithy
19
Session Layer


The session layer allows application on
separate computers to share a connection
called a session. This layer provides services
such as name lookup and security to allow
two programs to find each other and establish
the communications link.
The session layer also provides for data
synchronization and checkpointing so that in
the event of a network failure, only the data
sent after the point of failure need be resent.
21December, 1997
COE Department * Dr. Elleithy
20
Session Layer

This layer also controls the dialog between two
processes, determining who can transmit and
who can receive at what point during the
communication. This session service is called
token management. For some protocols, it is
essential that both sides do not attempt the same
operation at the same time. To manage these
activities, the session layer provides a token that
can be exchanged. Only the side holding the
token may perform the critical operation.
21December, 1997
COE Department * Dr. Elleithy
21
Presentation Layer

Unlike all the lower layers, which are just
interested in moving bits reliably from here to
there, the presentation layer is concerned with
the syntax and semantics of the information
transmitted. A typical example of a
presentation service is encoding data in a
standard agreed upon way.
21December, 1997
COE Department * Dr. Elleithy
22
Presentation Layer

The presentation layer translates data
between the formats the network requires and
the formats the computer excepts. This layer
does protocol conversion, data translation,
compression and encryption, character set
conversion, and the interpretation of graphics
commands.
21December, 1997
COE Department * Dr. Elleithy
23
Presentation Layer

The network redirector operates at this level.
The network redirector is what makes the files
on a file server visible to the client computer.
The network redirector also makes remote
printers act as though they are attached to the
local computer.
21December, 1997
COE Department * Dr. Elleithy
24
Application Layer

It provides services that directly support user
application, such as database access, e-mail,
and file transfers. It also allows applications to
communicate with applications on other
computers as though they were on the same
computer.
21December, 1997
COE Department * Dr. Elleithy
25
Application Layer

Examples
» WWW
» FTP
» e-mail
» USENET
» Multimedia
21December, 1997
COE Department * Dr. Elleithy
26
Network Layer
Khaled M. Elleithy, Ph.D
[email protected]
Department of Computer Engineering
King Fahd University of Petroleum and
Minerals
Dhahran, Saudi Arabia
Topics Covered in this Session



Services to the Transport layer
Routing
Congestion control
21December, 1997
COE Department * Dr. Elleithy
28
Services

The boundary between the network layer is
the boundary between the subnet (the set of
all routers) and the host. In other words, the
services provided by the network layer are the
services provided by the subnet.
21December, 1997
COE Department * Dr. Elleithy
29
Services Specifications



The services should be independent from the
subnet technology
The transport layer should be shield from the
number, type, and topology of the subnets
present
A uniform numbering plan should be used
across LANs and WANs
21December, 1997
COE Department * Dr. Elleithy
30
Services types

Connectionless
» The packets carry its full destination address and
sent independently of other packets. All error
detection, correction and flow control is done in the
host.
» Argument: the subnet is unreliable no matter who it
is designed.
21December, 1997
COE Department * Dr. Elleithy
31
Services types

Connection oriented
»
»
»
»
Establishment of connection
Negotiating Qos
Transmission session
Connection oriented
21December, 1997
COE Department * Dr. Elleithy
32
Services types

The argument of connection oriented vs.
connectionless is a question of where to put
the complexity: in the network layer or in the
transport layer?
» Both classes of services are allowed in the OSI
model.
21December, 1997
COE Department * Dr. Elleithy
33
Internal Organization

Virtual Circuits (VCs)
» Used with connection oriented service
» A route from the source machine to the destination
machine is established in setup
» The route is used for all traffic
» When the connection is released, the VC is
terminated
21December, 1997
COE Department * Dr. Elleithy
34
Internal Organization

Datagrams
»
»
»
»
No routes are worked out in advance
Each packet is routed independently
Successive packets many follow different routes
Adapt easily to failures and congestion
21December, 1997
COE Department * Dr. Elleithy
35
Comparison
Issue
Datagram
VC
Circuit setup
Not needed
Required
Addressing
Each packet contains full
source and destination
address
Routing
Each packet is routed
independently
Effect of router None, excepct packets lost
failures
during crash
Congestion
Control
21December, 1997
Difficult
COE Department * Dr. Elleithy
All packets follow same
route, no need to carry
addresses
Route chosen at VC
setup
All Vcs that passed
through the failed
router are terminated
Easy
36
Routing

Design issues
»
»
»
»
»
»
Correctness
Simplicity
Robustness
stability
Fairness
Optimality
21December, 1997
COE Department * Dr. Elleithy
37

Adaptive
» Routing decisions are based on measurements or
estimates of traffic and topology

Non-adaptive
» Routing decisions are static. Don’t depend on
changing measurements
21December, 1997
COE Department * Dr. Elleithy
38
Classes of Routing Algorithms

Centralized Routing
» Collecting information from the entire subnet to
make optimal decisions

Isolated Routing
» Each router collects information from neighboring
routers

Distributed algorithms
» Using mixture of local and global information
21December, 1997
COE Department * Dr. Elleithy
39
Shortest Path Routing

Meaning of shortest path
»
»
»
»
Number of hops
Distance in kilometers
Mean queue length and transmission delay
In general, it is a weighted function using all the
above
21December, 1997
COE Department * Dr. Elleithy
40
Shortest Path Routing


It is a centralized routing algorithm. The
shortest path is computed between all pairs in
the subnet. The paths are stored in routing
tables in the routers.
If a certain router fails, the algorithm has to
compute all routes again.
21December, 1997
COE Department * Dr. Elleithy
41
Multipath Routing


When a packet arrives to a router, a certain
path is chosen from the different alternatives
in the routing table.
In case of VCs, the route is chosen at the VC
setup.
21December, 1997
COE Department * Dr. Elleithy
42
Centralized Routing

Examples
» Shortest path routing
» Multipath routing


Centralized routing works fine if the traffic
doesn't change frequently.
A Routing Control Center (RCC) is used to
compute the routing tables
21December, 1997
COE Department * Dr. Elleithy
43
Centralized Routing

Drawbacks
» Time consuming in delivering information,
computing tables, delivering tables.
» A failure in the RCC will cause the network to
crash.
» Routers closer to RCC get their tables faster than
others.
» Heavy traffic near the RCC
21December, 1997
COE Department * Dr. Elleithy
44
Isolated Routing

Examples
»
»
»
»
Hot potato
Backward learning
Delta routing
Flooding
21December, 1997
COE Department * Dr. Elleithy
45
Isolated Routing

Hot potato
» When packets arrive to the router they are
forwarded to the shortest queue without regard to
where this queue leads to.
» A static weight of the route can be combined with
the queue length as criterion for forwarding
21December, 1997
COE Department * Dr. Elleithy
46
Isolated Routing

Backward learning
» Include with each packet the identity of the source
and a counter that is incremented at each hop.
This counter is used by a router receiving the
packet to know how many hops to the source. This
information is kept in the router’s table and is
updated if better values are received later.
21December, 1997
COE Department * Dr. Elleithy
47
Isolated Routing

Delta routing
» A hybrid technique between centralized and
isolated routing
» A centralized step is done first through the RCC
» Based on local measurements the router can
chose among different alternatives provided by the
RCC
21December, 1997
COE Department * Dr. Elleithy
48
Isolated Routing

Flooding
» An incoming packet is sent to all the lines except
the incoming one
» A counter is initialized with the maximum number
of hops in the subnet
» The counter is decremented at each hop
» The packet is discarded when the counter reaches
zero to avoid circulation of packets.
21December, 1997
COE Department * Dr. Elleithy
49
Congestion Control
21December, 1997
COE Department * Dr. Elleithy
50
Congestion Control

Congestion can be brought by several factors:
» Routers are slow to keep the required
bookkeeping.
» Output links are slower than input links
21December, 1997
COE Department * Dr. Elleithy
51
Congestion Control
» Congestion tends to feed upon itself and
become worse. If a router discards a packet
because it doesn’t have an empty buffer to
queue the incoming packet, the discarded
packet will be transmitted later. Extra traffic
is pumped in the subnet which causes
congestion to buildup.
21December, 1997
COE Department * Dr. Elleithy
52
Algorithms



Preallocation of buffers
Packet discarding
Choke packets
21December, 1997
COE Department * Dr. Elleithy
53
Preallocation of Buffers
» The call request packet marks routing tables when
a VC is setup.
» The call request packet reserve the required
buffers for the VC.
» If the required buffers aren’t available in advance,
the VC can't be established
21December, 1997
COE Department * Dr. Elleithy
54
Packet discarding
» Nothing is reserved in advance.
» If a packet arrives to a router and there is no buffer
to queue it, it is discarded.
» The discarded packet will be retransmitted later by
the sender.
» Piggybacked acknowledgements may be lost due
to packet discarding
21December, 1997
COE Department * Dr. Elleithy
55
Choke packets
» A mechanism that is triggered only when the
system starts to be congested.
» The router monitor the utilization levels of output
lines.
» Whenever an output line exceeds a certain
threshold, it becomes in a warning state.
» Choke packets are sent to hosts using lines in
warning state to reduce the traffic.
21December, 1997
COE Department * Dr. Elleithy
56
Choke packets
» The host reduces the traffic.
» After sometime the host can increase the traffic if
no choke packets are coming from the same
router.
21December, 1997
COE Department * Dr. Elleithy
57
Flow Control


Flow control is used to control the traffic
between to hosts. Host (A) can't send traffic to
host (B) that it can't handle although the
subnet may be able to handle.
Does flow control solves the congestion
problem? Why?
21December, 1997
COE Department * Dr. Elleithy
58
Other issues

There are other issues related to the network
layer that are discussed in other sessions,
such as:
» Internetworking (How networks differ,
fragmentation, firewalls)
» The network layer in the Internet (IP protocol)
21December, 1997
COE Department * Dr. Elleithy
59
21December, 1997
COE Department * Dr. Elleithy
60