Transcript Computer Networks_introduction

Computer Networks
Generic Types of Computer
Networks
Depending on the number of nodes and their proximity,
three types of computer networks can be identified:
1.Local area network (LAN): It connects hundreds of
computers, and the distance is up to a few kilometers.
2.Metropolitan area network (MAN): It connects
thousands of computers in a metropolitan area within a
distance of hundreds of kilometers.
3.Wide area network (WAN): It connects tens of
thousands of computers distributed throughout a country
or the world at a typical distance of thousands of
kilometers.
Network Architecture (Layering)
• To reduce their design complexity,
most networks are organized as a
series of layers, i.e., network
protocols are designed in terms of
layered architecture (layering).
• The major advantage of layering is
that it clearly delineates the
responsibilities of various protocols,
by dividing responsibilities
hierarchically among layers, with
each layer offering services needed
by the layer above.
• The key to protocol families is that
communication occurs logically at
the same layer of the protocol in
both sender and receiver, but it is
implemented via services of the
lower level (peer-to-peer).
Layer 7 protocol
7
7
Layer 6 protocol
6
6
5
5
4
4
3
3
2
2
Layer 1 protocol
1
1
Physical medium
Layering Contd.
• The danger in layering is the considerable latency added to
message delivery. However, protocol families are used to define a
standard, not to force how the standard is implemented.
• The most popular network architectures are OSI architecture and
TCP/IP (transmission control protocol/internet protocol) architecture.
Application
Presentation
Session
Transport
Network
Data Link
Physical
OSI Layers
Application
Transport
Network
DataLink
Physical
TCP/IP Layers
OSI reference model
7
6
5
4
3
2
1
•
•
Application
Application 7
Presentation
Presentation 6
Session
Session
5
Transport
Transport
4
Network
3
3
3
Network
3
Data Link 2
2
2
Data Link
2
Physical
1 1
1
Physical
1
Host A
Host B
The common purpose of layers 4-7 is to provide
interoperability: all the system elements can exchange data
regardless of the vendor of the equipment (open system).
Connectivity is provided in the layers 1-3 of the model, which
provides a working connection between the sender and
receiver, i.e., the ability to move data anywhere in the network,
regardless of the transmission technology or medium.
OSI: Application layer
 This layer's responsibility is to interface the user
application with the rest of the layers in the model. The
Application layer is also responsible for providing an API
(Application Programming Interface) to the user
applications so the programmers who write code for the
user interface don't have to worry about the
implementation details of the interface. This means that
the Application layer takes the responsibility of the
networking details away from the user application so the
user application does not have to know anything about
the underlying implementation of the network. Some
examples of user applications are file transfer services,
printing services, e-mail services, network management
consoles, client-server processes, and so on.
OSI: Presentation layer.
 This layer's responsibility is to provide encoding standards for
the network. The Presentation layer is also responsible for
negotiating between the Application layer and the rest of the
protocol stack. It provides a standard encoding streamer for
the Application layer so that communication between the
Application layer and the rest of the protocol stack is
standardized across different operating environments. In other
words, the Presentation layer provides translation and
conversion functions to successfully transfer data to the
underlying protocol stack. As an example, if the Application
layer of a PC sends information in ASCII format, the
Presentation layer is responsible for formatting the information
in the standard network type. This standard network type,
which is generic for the underlying protocol stack across
different operating environments, would be transferred without
further conversion. At the receiving end, it is again the
Presentation layer's responsibility to convert the generic
network format to a format that the receiving application can
understand. Data encryption and decryption can also take
place at the Presentation layer.
OSI: Session layer.
 This layer's responsibility is to provide a
communication channel between hosts. It
provides a definition for managing the
individual network channels, also called
sessions, between two hosts. The Session
layer is responsible for establishing a
session between the hosts, as well as
maintaining and ending the session. Some
examples of the Session layer protocol are
RPC (Remote Procedure Call), AppleTalk,
and NFS (Network File System).
OSI: Transport layer.
 This layer's responsibility is to control the transmission of data
on the network. In other words, it provides flow control
mechanisms to ensure data integrity between the nodes. The
flow control mechanism acknowledges the receipt of every
segment from the sending host and the proper sequencing of
the segments. If the sender does not receive an
acknowledgement from the recipient, the flow control
mechanism at the sender's end is responsible for resending
the segment. On the whole, the Transport layer's
responsibility is to segment the data received from the
Session layer and forward it to the Network layer. In addition,
the Transport layer receives segmented data from the
Network layer to reassemble the segments to forward them to
the Session layer. The Transport layer is also responsible for
establishing a logical connection between the destination
node and the source node. Some examples of the Transport
layer are TCP and UDP (User Datagram Protocol).
OSI: Network layer.
 This layer's responsibility is to ensure the
addressing of the hosts. It also ensures
the routing of information between hosts
across networks. In other words, the
Network layer handles all of the
transmission and traffic management
among hosts. It also provides address
resolution for the segments forwarded by
the Data Link layer.
OSI: Data Link layer.
 This layer's responsibility is to define how data is accessed
from a physical medium. It provides a mechanism to format
the information presented from a physical medium so the
information can be passed to the Network layer. The
information presented from a physical medium can be in the
form of bits. The Data Link layer collates this information and
formats it into frames. A frame is a unit of information that
contains the destination address, the source address, an error
checksum, and the data itself. The Data Link layer is also
responsible for converting the information obtained from the
Network layer into bits to forward it to the Physical layer. In
addition, the Data Link layer is responsible for ensuring that
the messages traversing the network reach the appropriate
physical devices. This is possible because the Data Link layer
manages the unique identity of the physical device on the
network. It uses the concept of hardware addressing (MAC
address) to identify a physical device. Some examples of the
Data Link layer protocol are ARP (Address Resolution
Protocol) and RARP (Reverse Address Resolution Protocol).
OSI: Physical layer.
• This layer's responsibility is to manage the hardware
details of sending and receiving binary data over a
physical channel. The physical channel is typically made
up of wires such as twisted-pair and fiber optic cables. It
can also be made up of wireless media such as infrared
or radio waves. In general, the Physical layer provides a
specification for interfacing with a physical channel
based on the electrical and mechanical functions of the
medium. The connectors at the Physical layer have
different topologies defined for different network designs.
Topologies are the structures in which you set up your
network. Some examples are the star topology, the ring
topology, and the bus topology. One example of the
Physical layer is the Ethernet standard, which is the
network protocol that defines how different devices on
the network communicate with each other over the
Physical layer.
TCP/IP reference model
• 5 layers
• Application layer. This layer's responsibility is to
provide a common interface for any user application
to communicate with the underlying layers. In other
words, the Application layer is responsible for
providing an interface between the user application
and the network.
Application Layer
Transport Layer
Network Layer
Data Link
Physical
• Transport layer. This layer's responsibility is to control the flow of data
between two communicating hosts. The Transport layer is responsible for
breaking down data into packets and sending and receiving them from the
Network layer.
• Network layer. This layer's responsibility is to route packets across the
network. It is also responsible for some message control and group
management.
• Link layer. This layer's responsibility is to handle the hardware-related details
of the system. In other words, the Link layer is responsible for interfacing the
operating system to the network interface card within the computer.
TCP/IP enabled communica
Internetwork communication
Homework
• Compare OSI and TCP/IP model
LAN Components
•
3 general characteristics:
–
–
–
•
•
•
•
•
A diameter of not more than a few kilometers.
A total data rate of at least several Mbps.
Completely ownership by a single organization.
The medium in LAN is usually a twisted pairs of copper
wires, or coaxial cable, or fiber optics. It may also be
wireless transmission.
Hardware in LAN includes network interface cards (NICs),
servers, communication devices.
NIC connects a machine to LAN.
Server provides service to other machines.
Communication devices include repeaters, bridges, routers,
and gateways etc..
LAN components
• Repeaters copy individual bits
between cable segments.
• Bridges connect LANs together.
• Routers or gateways connect
LANs to WANs or WANs to
WANs and resolve incompatible
addressing.
LAN server
Repeater
Host
Other LAN
Router
Bridge
To WAN router
LAN Communication Concepts
•
•
•
•
In LAN, network control is distributed among the
devices on the network, it resides in the NIC firmware
in each machine.
LAN communication may be connectionless or
connection-oriented.
Connectionless messages (datagrams) are sent with
the expectation that they will be received correctly.
There is no acknowledgment of correct receipt. A
higher layer must ask for retransmission if the
message is received incorrectly.
Connection-oriented communications include the
acknowledgment of message as correct before they
are passed on to the recipient.
Comm. Concepts contd.
•
•
•
•
•
•
LANs have five major communications characteristics:
Medium: the means by which data is sent.
Transmission technique: In baseband technique, the
LAN signal is carried directly on the medium; in
broadband system, the LAN signal is modulated on to
an analog carrier signal, which allows several LANs to
share the same medium.
Network topology: the layout of the cabling.
Access control method: contention (Ethernet) and
token passing (token ring) for shared medium.
Data Rate: the raw ability to transfer information in
megabits per second.
Comm. Concepts contd.
• In LANs, the machines can be connected by
shared medium or switched (point-to-point)
medium.
• Shared medium: Multiple computers share a
single interconnection medium (Ethernet).
• Switched medium: It allows communication
directly from source to destination, without
intermediate nodes to interfere with these
signals.
WAN
• Wide area networks (WANs) carry message at a lower
speed between computers that are separated by large
distance.
• Many WANs and LANs can be combined to produce a
single internetwork – a communication system that
interconnects large collections of geographically
dispersed computers.
• The computers interconnected by a WAN are called host
computers. The communication medium is a set of
communication circuits linking a set of dedicated
computers called packet switches or packet switching
exchanges (PSEs).
• The OSI layer architecture, TCP/IP layer architecture, or
other layer architectures can be used in building WANs.
WAN
• In WANs (packet networks), a message is
divided into packets before transmission and the
packets are reassembled at the receiving
computer (transport layer). A packet consists of
a header and a data field. The header contains a
transport address composed of the network
address of a host and a port number.
• The PSEs operate the network by forwarding
packets from one PSE to another along a route
from sender to the recipient. PSEs are
responsible for defining the route (network
layer).
WAN
• Every packet of data is stored temporarily by
each PSE along its route before it is forwarded
to another PSE (store-and-forward
communication). The routing operations
introduce a delay at each point in the route, and
the total transmission time for a message
depends on the route it follows.
• Two types of data transport service can be
provided: connection-oriented -- a `virtual
connection is set up between a sending and a
receiving process and is used for the
transmission of a stream of data; connectionless
– individual messages (datagrams) are
transmitted to specified destinations.
Intranet
10
12
T2
15
DATA
87
19
10
A
87
SW2
LAN
LAN
SW1
LAN
LAN
SW3
D
Internet
A
S1
D
S3
A
S2
F2
F1
LAN
LAN
S1
F1
F2
LAN
F3
WAN
F1
F2
LAN
S3
D
Introduction to DLL
• Receives service from physical layer and
provides service to the network layer.
• Receives service from network layer and
provides service to physical layer.
• Responsible for carrying data from one
hop to the next hop.
10
12
T2
15
DATA
87
19
10
87
Duties
bridge
15
87
12
19
Duties of DLL
packetinzing
Addressing
Frame or cell
MAC or VC
Error control
Flow control
CRC
DLL is for point to point, or node to node on a common link
LAN and WAN operate in DLL
Access control
Prevent
conflict or
collision
IEEE standards
• 802 project
- LLC (logical Link Control)
- MAC (Media Access Control)
802.3:CSMA/CD
802.4: TOKEN BUS
802.5: TOKEN RING
802.6: DQDB
802.11: WIRELESS LAN
MAC
DLL
LLC
PHYSICAL
LAYER
IEEE
PHYSICAL
LAYER
INTERNET
Design issues
• How to perform the duties stated in the
last slide?
• DL can be designed to offer various
services. 3 main responsibilities:
– Unacknowledged Connectionless service.
– Acknowledged connectionless service.
– Connection oriented service.
Connection oriented service
• A connection is established before the data is sent. Each
frame sent is numbered, and DL guarantees that the
frame is indeed received. Each frame is received only
once and in right order.
• Transfers have 3 distinct phases.
– Connection establishes by initializing variables and counters
needed to keep track of frames received.
– One or more frames are transmitted
– Connection released by freeing variables, buffers and other
resources to maintain the connection.
Framing
• Packetizing. Hand over the frame to
physical layer. Or create frames from raw
data received from physical layer.
• Breaks up bit streams into discrete frames
and compute checksums for each frame.
– Frame gap; in addition to this
• Character count; rarely used now
• Starting and ending character with character
stuffing
• Start, end flags with bit stuffing
• Physical layer coding violation
• Problem with character count
– count character may be corrupted.
• Character delimiter
– ASCII character sequence used as frame delimiter
– When delimiter appears in the data consecutive
delimiter character is used as a escape sequence.
• Suitable for 8-bit character and ASCII code
transfer.
• Start, end flags with bit stuffing
– Start bit pattern: 01111110
– If there are consecutive 5 1s on the data, DLL
automatically stuff a 0 bit after the consecutive 5 1s in
the outgoing bit pattern. Receiver remove this 0 bit
after the consecutive 5 1s.
• Use different encoding for data and frame
separator.
– Manchester encoding represent 1 by H-L and 0 by LH. H-H and L-L are not used for data. One can use HH-L-L as frame delimiter.
Error control
•
•
•
•
•
•
Need feedback for sending frames.
Waiting time for feedback: timer.
Retransmit if frame or the acknow is lost.
Potential danger to retransmitting.
Use sequence number to each outgoing frame.
Whole issue is of managing timers and
sequence numbers so as to ensure that each
frame is ultimately passes to the NL at the
destination exactly once.
Flow control
• How does a recv handle the situation
when a sender sends frames faster than it
can receive.
• Sender need feedback from recv to control
its frame rate.
Access control
• Link management
Elementary data link protocols:
Flow control protocols
• Physical, data link and Network layers are independent. Uses
message to communi.
• Connection oriented, reliable channel.
• Infinite supply of data.
• No processing delay.
• Simplex mode.
• DL waits for a packet form NL. When and if DL recv a pack from NL,
it encapsulates it into a frame adding some control bits (header),
and then handed over to physical layer. Transmitting HW appends
checksum bits and then transmits frame on the cable.
• DL in rcvr waits for a frame from physical layer. DL may wait in an
infinite loop or for an interrupt from physical layer. Recv HW recv a
frame and computes the checksum. If checksum is ok frame is recvd
undamaged and passed to DL. DL checks if the destination matches
with its own id. If everything is ok, DL drops the frame header and
passed the packet to NL.
Definitions
const LastBit = ….; {determines the pkt size}
doomsday = false; {repeat forever}
MaxSeq = ….; {Highest Seq = 2n -1}
type bit = 0..1;
SequenceNr = 0 .. MaxSeq;
packet = packed array [0 .. LastBit] of bit;
FrameKind = (data, ack, nak);
Frame = packed record
kind: FrameKind;
seq: SequenceNr;
ack: SequenceNr;
info: packet;
end;
Definitions contd.
procedure wait (var event: EvType);
begin {wait for an event to happen; return its type in event} end.
procedure FromNL(var p: packet);
begin {Fetch info from NL for transmission} end;
procedure ToNL(p: packet);
begin {delivers info from inbound frame to NL} end;
procedure FromPhysL(var r: frame);
begin {get an frame from PhysL and copy it to r} end;
procedure ToPhysL(s: frame);
begin {pass the frame s to PhysL for transmission} end;
procedure StartTimer(k: SequencNr);
begin {start the clock and enable TimeOut event} end;
Definitions contd.
procedure StopTimer(k:SequenceNr);
begin {Stop the clock and disable TimeOut event} end;
procedure StartAckTimer;
begin {Start aux timer for sending separate acks} end;
procedure StopAcktimer;
begin {Stop aux timer and disable NLIdle event} end;
procedure EnableNL;
begin {allows NL to cause a NLReady event} end;
procedure DisableNL;
begin {Forbids NL from causing a NLReady event} end;
procedure inc(var k: SequenceNr);
begin {increment k circularly} end;
Unrestricted simplex protocol
Assumptions: Data trans in one direction only. Channel error free. No
processing delay. Infinite buffer space.
Sender DL protocol:
type EvType = (FrameArival);
procedure sender1;
var s: frame;
buffer: packet;
begin
repeat
FromNL (buffer);
s.info = buffer;
ToPhysL(s);
until doomsday
end;
Receiver end DL:
procedure receiver1;
Var r: frame;
event: EvType;
begin
repeat
wait(event);
FromPhysL(r);
ToNL(r.info);
until doomsday;
end;
Simplex wait-and-Stop protocol
The main problem we have to deal with is how to prevent sender
from flooding the recevr with data faster than it can handle.
Assumption: recev has limited buffer, needs time to process
frames. Needs mechanism to control the rate of frame-flow
from sender.
• If the recvr requires a time t to execute FromPhysL+ToNL, the
sender must transmit at an average rate less than one frame
per t time. Moreover, recvr HW my not have automatic buffer
and queuing.
• Recvr sends a dummy frame as the feedback => Ack.
• Sender wait for Ackn before it sending the next frame.
• A half-duplex physical channel is sufficient here.
type Evtype = (FrameArrival);
procedure sender2;
var s:frame;
buffer: packet;
event: EvType;
begin
repeat
FromNL(buffer);
s.info = buffer;
ToPhysL(s);
wait(event);
until doomsday
end;
procedure receiver2;
var s,r: frame;
event: EvType;
begin
repeat
wait(event);
FromPhysL(r);
ToNL(r.info);
ToPhysL(s);
until doomsday;
end;
Stop and Wait protocol for Noise
channel
• Sending device keeps a copy of the last frame transmitted until it recvs an
ack for that frame.
• Both data frames and ack frames are numbered alternatively 0 and 1. A data
0 frame is ack by an ACK 1 frame, indicating that it has recved data frame 0
and expecting data frame 1.
• If the recvr detects an error in the recevd frame, it simply discard the frame
and send no ack. If the recvr recives a frame out of order, it knows that a
frame is lost. It discards the out-of –order recvd frame.
• Sender has control variable S, that holds the number iof the recently sent
frame (0 or 1). The rcvr has a control variable, R, that holds the number of
the next frame expected (0 or 1).
• The sender starts a timer when it sends a frame. If an ack is not received
within timeout period, the sender assumes that the frame is lost and
resends it.
• Rcvr sends only positive ack for frames received safely. Ack number always
defines the next frame expected.
Operation: Normal
S=0
Data 0
R=0
S=1
Data 1
R=1
time
Lost frame
• A receiver remains
silent and keeps it
value of R.
• After the time out
interval at the
sender ends,
sender sends
another copy of the
frame.
Lost Acknowledgement
• If the sender receives
a damaged Ack, it
discards it.
• When the timeout for
Ack is over sender
retransmits the frame.
• However, receiver
discards the duplicate
frame and sends the
Ack again.
Delayed Ack
• Ack is received by
the sender after the
timeout for ack 0.
The sender already
retransmitted a copy
of the frame 0.
• Since receiver
expects the frame 1,
it simply discards the
duplicate frame 0 and
sends ack 1.
Piggybacking
• Bidirectional
transmission.
• Piggybacking
combines data frame
with acknowledgment
Sliding window protocols
• To improve efficiency multiple
frames (outstanding frame) are
sent:
– Go back N
– Selective repeat
• Frames are numbered
sequentially from 0 to 2N-1. If N
is 3, frames are:
0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,
0,1,2,3,…..
• Sliding window concept is
used to hold the outstanding
frame.
Senders sliding window
Receivers 1 bit sliding window
• Always 1 bit window.
• Hold outstanding frame;
the frame to be received
next.
Control variables
•
•
•
•
S – seq.no of recently sent frame.
SF – seq. no of the first frame in the window.
SL – Last frame in the window.
R – seq no of the frame it expects to receive.
Acknowledgement
• If a frame is damaged or is received out of
order, the recv is silent and will discard all
subsequent frames.
• The silence of the recv. cause the timer of
the unacknowledged frame in the sender
to expire. Then sender go back to send all
frames, beginning with the
unacknowledged one.
Go back N normal operation
Lost or damaged frame
Sender window size
• Window size must be less than 2m.
• Otherwise recv can recv erroneous packet.
• Piggybacking is possible to implement bidirectional transmission.
• Q: Explain the problem that can result in if the window size is
larger than or equal to 2m.
Selective repeat
• In noisy channel Go back N protocol is inefficient.
Retransmission is high.
• Selective repeat protocol does no sent N frames; only
the damaged frame is retransmitted.
• Sender and receiver window size must be less than or
equal to 2m/2.
• Use Nack to report damaged frame.
3| 0| 1| 2| 3| 0 | 1
Frame
acknowledged S S S
F
L
3| 0| 1| 2| 3| 0 | 1
Frames waiting Frames received
RF RL
to be sent
& acknolgd
Sender window
Frames that cannot
be accepted
Receiver window
Selective repeat operation
• Frame 0 and 1 are
received b’coz they are in
the range at the receiver.
• When frame 3 is received,
it is also accepted,
however, receiver sends
nack for 2.
• Sender then sends only
frame 2.
• Try yourself: what happes
for lost and delayed acks
and nacks??
Explain that the size of sender and
receiver window must be at most
one-half of 2m.
HDLC: configuration and Transfer modes
HDLC: High level data link control. Half-duplex and fullduplex. Provides 2 common modes of transmission:
NRM: Normal Response mode
One primary many secondary.
Secondary can only responds.
Primary can send commands.
Used for both p2p and
multipoint.
ABM: Asynchronous
balanced mode
P2p. Each station can
function as a primary and
secondary.
HDLC: frame format
Flag
•
Three types of frame:
–
–
–
•
•
•
Information. Its length can vary from network to network but always fixed within each
network.
Checksum
–
•
•
1 or 2 bytes long. Sequence no., ackn., etc. flow control.
Data
–
•
I frames: Information frames – used to transport user data & control info relating to data.
S frames: Supervisory frames – used to transport only control information.
U frames: Unnumbered frames – for system management.
Bit oriented. Use bit stuffing.
Address: 1 or several bytes long. Ethernet uses more bytes for both sender and
receiver addresses.
Control
–
•
Flag
Error control
On idle, flags sequences are transmitted continuously
Minimum frame length three fields (32 bits)+flag bits.
HDLC contd.
Seq – frame sequence no. 3 bit sliding window. Next – piggybacked
ackn. P/F – poll/final, P is used when computer is inviting the
terminal to send data. All the frames sent by the terminal set the
bit to P, except the final one, which is set to F.
Information
Supervisiony
Unnumbered
Control fields for three kinds of frames
• In some of the protocols the P/F bit is used to force the other
machine to send a supervisory frame immediately rather than
waiting for the reverse traffic onto which to piggyback the window
information.
• Type – for different kinds of supervisory frames. Type 0 is RECEIVE
READY, 1 is REJECT. Next field indicates frames to be
retransmitted, Type 2 – receive not ready, Type 3 - selective reject.
• Unnumbered Frames – used for connectionless services. Differs
greatly on implementation.
PPP
• Point to Point Protocol
• Purposes:
– router to router traffic
– home user to ISP
• provide three main features:
– Framing. Frame format also handles error detection
– Link control protocols for bringing lines up, testing them,
negotiating options, and bringing them down when necessary.
This protocol is called link control protocol (LCP). Supports
sychronous and asynchronous circuits and bit and byte oriented
encoding.
– A way to support different network layer protocols. Network
Control protocol (NCP).
Moreover, PPP suports multiple protocols, allows IP address to be
negotiated at connection time, permits authentication.
Working of PPP for User to ISP
•
•
•
PC first calls the provider’s router via modem. After the router modem has
answered the phone and established a physical connection, the PC sends
the router a series of LCP packets in the payload field of one or more PPP
frames. These packets and their responses select the PPP parameters to
be used.
once the parameters have been agreed upon, a series of NCP packets are
sent to configure the network layer. Typically the pc wants to run a tcp/IP
protocol stack, so it needs an IP address. Usually, ISP dynamically assigns
one IP to each newly attached PC for the duration of its login session. NCP
does this job.
PC is now connected to internet, and can send/ receive data just like a host
connected to a LAN. When the user is finished, NCP tears down the
network layers connection and frees up the IP. then LCP shuts down the
datalink layer connection. Finally the PC tells the modem to hangup the
phone, releasing the physical layer connection.
PPP Frame format
Flag
1 byte
01111110
Address
1 byte
Control
1 byte
protocol
1 or 2
variable
2 or 4
flag
11111111
00000011
protocol
payload
chekcum
01111110
flag, address and control bytes are fixed
protocol: tell what kind of packet is in payload. LCP, NCP, IP, IPX,
AppleTalk
payload length is negotiated. default is 1500bytes.