1
CSC- 362 Computer Networks
Week-8 Lecture-15-16
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2000
2
Instructor Contact Details
Name: Mr. Attique Ur Rehman
Course Instructor: CSC362- Computer Networks
Credit Hours: (3+1)=4
Office Location: 2nd Floor Computer Science Faculty Office:
41-C
Email:
[email protected] Visiting Hours: Wednesday (11:30 am -1:00 pm)
Lahore Garrison University
3
Course Material
Reference books
Many textbooks on Networking may be consulted
Research papers!
RFCs and Internet drafts
Related to TCP/IP suite and other protocols
Web resources
Tutorials, white papers, reports, etc.
Lahore Garrison University
4
Text Book
Computer Networks: A Systems Approach by Larry L. Peterson and Bruce S. Davies.
Third Edition [2003], Morgan Kaufmann Publishers, San Mateo, California, USA
Computer Networks by Andrew S. Tanenbaum
Fifth Edition
Data Communication and Computer Networks, by Behrouz A. Forouzan
5th Edition
Data and Computer Communications by William Stallings
10th Edition
Computer Networking: A Top-Down Approach Featuring the Internet by James F. Kurose and Keith
W. Ross
6th edition
Lahore Garrison University
5
The Big Picture
You
are
here
03/20/24
6
What we know …
Elements of networks: nodes and links
Building a packet abstraction on a link
Transmission, and units of communication data
Detecting transmission errors
Simulating an error-free, reliable channel
Sliding window mechanism
Arbitrating access to a shared medium
Design issues of direct link networks
Functionality of network adaptors
03/20/24
7
What Next …?
LANs do not normally operate in isolation. They are
connected to one another or internet
To connect LANs or segments of LANs connecting devices
are used.
Connecting devices operates in different layers of internet
model.
This chapter discuss which operates at physical and data link layer
03/20/24
8
Connecting Devices
Passive hubs
Repeater/Active hubs
Bridges or two layer switches
Routers or three layer switches
Gateways
03/20/24
9
Passive hubs
A passive hub is just a connector
It connects the wires coming from different branches
In star topology Ethernet LAN
a passive hub is a point where the signal coming from different nodes collide.
The passive hub is a collision point.
Passive hub is a part of transmission media and operate below the
physical layer
03/20/24
10
Repeater
A repeater is device which operates only in the physical
layer
It receives a signal and before, it becomes too weak or
corrupted, regenerate the original bit pattern.
The repeater sends the refreshed signal.
A repeater can extend the physical length of a LAN
03/20/24
11
Repeater
A repeater connects segments of a LAN.
A repeater forwards every frame – there is no filtering.
A repeater is a regenerator, not an amplifier.
03/20/24
12
Function of Repeater
03/20/24
13
Active Hubs
An active hub is a multi-port repeater, used in star-wired
LANs (Ethernet).
Operate at physical link
Because of the amount of traffic and collisions, hubs can
only be used in small network configurations.
03/20/24
14
Building Extended LANs
Traditional LAN
Shared medium (e.g., Ethernet)
Cheap, easy to administer
Supports broadcast traffic
Problem
Scale LAN concept
Larger geographic area (> O(1 km))
More hosts (> O(100))
But retain LAN-like functionality
Solution: bridges
03/20/24
15
Bridges
Connect two or more LANs with a bridge
Operates in both physical and data link layer
as a physical device, it regenerates the signal it receive.
as a data link device, it check the MAC address of source and destination contained in the
frame.
Transparently extends a LAN over multiple networks
Comprises 2 to 4 ports
accept and forward strategy (in promiscuous mode)
level 2 connection (does not add packet header)
A B C
Port 1
Bridge
Port 2
03/20/24
X Y Z
16
Switches
Switches like bridges are used to connect the subdivided segments of
networks.
It is a Layer 2 devices. Operate at the Data Link Layer (Layer 2) of
the OSI Reference Models.
Switches use the best of hubs and bridges while adding more abilities
Multi-port ability of hub
Filtering ability of a bridge
03/20/24
17
Switches
Switches can perform error checking before forwarding data.
which are very efficient by not forwarding packets that error-end out or
forwarding good packets selectively to correct devices only.
Network Switches and Bridges have many similarities and similar
function.
But Switches are considered as superior devices than bridges.
03/20/24
18
Bridges vs. Switches
Packet forwarding
Bridges are performed using software.
Switches are performed using hardware/ASICs (Application Specific Integrated Circuits).
Speed
Switches operate comparatively higher speeds as compared to bridges.
Method of switching
Bridge is store and forward.
Switch can be store and forward, cut-through or fragment-free.
03/20/24
19
Bridges vs. Switches
Number of Ports
Switch has more ports than a Bridge.
Operational Mode
Bridges can operate only in half duplex mode
Switch can operate both in half duplex or full duplex mode.
Switches support full-duplex LAN communication.
Collision Domain
Both Bridge and Switch has one collision domain per port, but switches have
one broadcast domain per VLAN.
03/20/24
20
Network with Hub-Bridge
03/20/24
21
Network with Switch
03/20/24
22
Learning Bridges
Trivial algorithm
Forward all frames on all (other) LAN’s
Potentially heavy traffic and processing overhead
Optimize by using address information
“Learn” which hosts live on which LAN
Maintain forwarding table
Only forward when necessary (dest. not on same LAN)
Reduces bridge workload
03/20/24
23
Learning Bridges
Learn table entries based on source address
Timeout entries to allow movement of hosts
Table is an optimization; need not be complete
Always forward broadcast frames
Uses datagram or connectionless forwarding
Host Port
A 1
A B C
B 1
C 1
Port 1
X 2
Bridge
Y 2
Port 2
Z 2
X Y Z 03/20/24
A Bridge Connecting two LANs 24
A bridge does not change the physical (MAC) addresses in a frame.
03/20/24
25
A Learning Bridge and Process of Learning
03/20/24
26
Learning Bridges
B
B3
C B5
D B7
B2 K
E F
B1
G H
B6 B4
Problem
I
J
Redundancy (desirable to handle failures, but …)
Makes extended LAN structure cyclic
Frames may cycle forever (loop problem)
Solution: spanning tree 03/20/24
27
Loop Problem in Learning Bridges
Solution: Spanning Tree 03/20/24
28
Spanning Tree
Subset of forwarding possibilities
All LAN’s reachable, but
A cyclic Bridges run a distributed algorithm to calculate the
spanning tree
Select which bridge actively forward
Developed by Radia Perlman of DEC
Now IEEE 802.1 specification
Reconfigurable algorithm
03/20/24
29
Spanning Tree Concept
LAN’s and bridges make a bipartite graph
Ports are edges connecting LAN’s to bridges
Spanning tree required
Connect all LAN’s: all vertices of a graph are covered
Can leave out bridges: all edges may not be covered
03/20/24
30
Spanning Tree Algorithm
Each bridge has a unique, totally-ordered identifier
Select bridge with lowest ID as root bridge
Each bridge determines
Direction of shortest path to root (preferred port)
For each connected LAN, is it the designated bridge?
Select bridge on each LAN closest to root as designated bridge
Use ID (lowest) to break ties)
Ports connecting LAN’s to designated bridges called designated ports
03/20/24
31
Spanning Tree Algorithm
All designated bridges forward frames
On all designated ports
On preferred port (path leading to root)
A
B
B3
LAN C B5
D B7
B2 K
Designated port
E F
Preferred port
B1
B2 Designated bridge G H
B6 B4
I
J
03/20/24
32
Example: Prior to Spanning Tree Application
What happens if you have a loop of
bridges/switches in your LAN?
03/20/24
33
Applying Spanning Tree
Step 1: Select the bridge with smallest ID as root bridge.
Step 2: Mark one port of each bridge (except root bridge) as the root/ proffered port. Root
port is the port with least-cost path from the bridge to the root bridge (marked with 1 star).
Step 3: For each LAN, choose a designated bridge. A designated bridge has the least-cost
path between the LAN and root bridge (the arrows). Mark the corresponding port that
connects the LAN to its designated bridge the designated port (two stars).
03/20/24
Applying Spanning Tree
34
Step 4: Mark the root port and designated port as forwarding ports, the
others as blocking ports (every port with 1 or 2 stars keep, ports with
no stars drop). Note - there is only 1 path between any two bridges.
03/20/24
35
Distributed Spanning Tree Algorithm
Bridges exchange configuration messages
ID for bridge sending the message
ID for what the sending bridge believes to be root bridge
Distance (hops) from sending bridge to root bridge
Initially, each bridge believes it is the root
Sends a configuration message, and checks if any received message is better than the
current best message
Each bridge records current best configuration message for
each port
03/20/24
36
Distributed Spanning Tree Algorithm
Bridges forward
A
configuration messages C
B3
B5
outward from root bridge B2
D B7 K
i.e., on all designated ports E F
Bridge assumes it is B1
G H
designated bridge for a
B6
LAN until it learns I
B4
J
otherwise
03/20/24
37
Algorithm Details
In steady state, only root generates configuration messages
periodically
Timeout restarts algorithm (claiming “I am root …”)
In steady state, only designated bridges forward configuration
messages
Outward from root bridge, to all designated ports
Until they learn they are not designated bridge
Although algorithm is reconfigurable, it is not possible to
forward frames over alternative paths
03/20/24
38
Broadcast and Multicast
Forward all broadcast/multicast frames to all preferred and
designated ports
Current practice
Lets hosts decide whether or not to accept frame
Alternative: extend learning to handle groups
Learn when no group members downstream
Group members periodically identify themselves
Accomplished by having each group member sending a frame to the bridge with group
address in source field
03/20/24
39
Uses and Limitations of Bridges
Extend LAN concept
Limited scalability
To O(1,000) hosts
Not to global networks
Not heterogeneous
Some use of address, but
No translation between frame formats
03/20/24
40
Limitations of Bridges
Do not scale
Spanning tree algorithm does not scale
Broadcast does not scale
Do not accommodate heterogeneity
Only supports networks with same address formats
Caution: beware of transparency
Frame drop because of bridge congestion
Large and variable latency between two hosts
Frames may reorder in extended LANs
03/20/24
41
Routers
A network device that forwards packets form one network to
another based on their logical or IP addresses (host-to-host
addressing).
Based on routing tables, routers read each incoming packet and
decide how to forward it.
Routers work at the network layer (layer 3) of the protocol.
A router normally connects LANs and WANs in internet.
03/20/24
42
Routers
Route traffic from one network to other.
It has routing table that is used for making decisions about
route.
A routing tables are normally dynamics and updated using
routing protocols.
Routers provides additional features like DHCP server,
NAT, Static routing,
03/20/24
43
Gateway
Device that converts one protocol or format to another
A network gateway converts packets from one protocol to
other.
Translate from one protocol to other.
Protocol conversion like VoIP to PSTN or Network
Access Control etc.
Does not support dynamic routing
03/20/24
44
Gateway
A gateway is normally a computer that operates in all five
layers of internet or seven layers of OSI model.
A gateway takes an application message, read it, and
interprets it.
It can be used as connecting device between two
internetworks that uses different models.
A network designed to use the OSI model can be connected to another network
using the Internet model.
A gateway connecting two systems can
Take a frame as it arrives from the first system
Move it up to the OSI application layer
And remove message
03/20/24
45
Implementation and Performance
The cost of processing small packets (parsing headers, deciding
output port) dominates other restrictions
Throughput = packets/sec x bits/packet
Moving data from inputs to outputs in parallel may increase the
aggregate throughput
Potential bottlenecks
I/O bus bandwidth
Memory bus bandwidth
Processor computing power
