Transcript Presentation9 - University Of Worcester

COMP1321
Digital Infrastructure
Richard Henson
University of Worcester
December 2015
Week 10: Routing
and Routing Mechanisms
Explain the fundamental differences
between documenting client-server and
peer-peer networks
 Explain the two fundamental types of
network routing
 Explain the system of network device
naming used for Internet routing

Let’s assume

IP addressing
all computers can be logically named with
unique IPv4/IPv6 addresses

MAC addressing
all computers have hardware addresses
“hardwired” into the network interface card
or connections on motherboard
Routing

Problem: how to get a message from
one computer/device to another, across
a network, or the Internet…
Comp
uter A
network
Comp
uter B
Requirements

1. Identify the destination

2. Find that destination

3. Choose/calculate the best pathway
to the destination through the network

4. Send the data…
Two problems

Involves movement of electrical signals
mustn’t collide..

Consistent naming and addressing to
allow data to be routed to the correct
destination (i.e. both MAC or both IP)
Subnetting

Logically arranging computers into
small, manageable numbers
less than 256
» in practice, 254
known as a subnet
IPv4 addressing follows this convention
» e.g. subnet 192.168.1.1 to 192.168.1.254
Approaches to routing
1: “Broadcast” Routing

Uses MAC addresses to send messages to
all available computers in the subnet
 only the computer to which it is addressed bothers
to read its contents


Useful on small local networks
Uses too much bandwidth for large networks
containing many subnets…
Managing Collisions
(contention)




Transmission of a data packet takes time…
Travel of the packet to the furthest point on
the network takes a further finite time…
If, at any time during this period, another host
on the network starts to transmit…
CRASH!!!
 signals cancel each other out…
Collision animation
from http://handsonhowto.com/lan102.html
Transmitter B
Transmitter A
Resolving contention
Protocols for human communication
 How do we decide who speaks?
 What rules do we use?
 Discuss in groups…

Resolving Contention

Possible solutions:
Polling
Token Passing
ALOHA
Polling



Central controller
interrogates each node
in turn and asks if it has
a message to send
If a message is waiting
to be sent, it is delivered
If no message, controller
passes on to the next
node…
Token passing
Software ‘token’ passed from node to
node in a predetermined order
 Nodes can only send messages when
they are in possession of the token
 Token is passed to the next node in
sequence when it is no longer needed

if no message is to be sent, or when the
message has been sent
Hardware token
from http://www.24carat.co.uk/wyrebustoken.html
“Aloha”

Rule:
each station transmits as and when
needed
Named after Hawaiian greeting
 Originally used to connect several
computers by radio in Hawaii

hard (cabled) links not practicable
Aloha (continued)

If a collision occurs, messages are
retransmitted after a random wait
If both stations retransmitted immediately,
a further collision would occur
OK for light traffic (and few collisions)
 Maximum efficiency possible about 18%
due to collisions

Commercial Aloha – “Ethernet”

Ethernet name derived from “the ether”
a hypothetical invisible substance that was
once thought to exist in space and allowed
radio waves to be conducted through it (!)

Coined by Dr Graham Metcalfe, Xerox
wanted to connect 100 computers together
over a 1km cable
used a system based on pure Aloha
Ethernet & Network
Contention

Pure ALOHA:
 nodes can attempt to broadcast at any time
 then manages the attempted broadcasts to ensure
that collisions are detected and dealt with by
resending

OK for lightly used network
 but… many concurrent connections on the same
network segment can create a lot of collisions
» result: severely reduced response time
Ethernet – CSMA to reduce
number of collisions

Strategy used in broadcast systems to
reduce the likelihood of collisions
CSMA = Carrier Sense Multiple Access

Each node listens before transmitting
if the medium is busy then the node waits
otherwise it transmits
Mechanism of CSMA

Problem: two nodes could begin to
transmit almost simultaneously
and not detect each other’s transmission
before starting their own message

Solution: each node listens while
transmitting to be sure that no other node
starts transmitting
CSMA/CD
CD = collision detect
 If a collision is detected:

both nodes stop transmitting
» would be a waste of time to finish message that
is corrupted…
 then wait a random time and retry
» binary exponential backoff algorithm!
Unslotted CSMA

Also known as “non-persistent” CSMA
 based on and replaces pure Aloha

Unslotted: any node can transmit at any time
 Some protocols only allow transmissions to start at
certain time – starts of ‘time ‘slots’

Non-persistent: nodes wait before retry
 if they both tried to transmit again immediately,
they would cause another collision!
Putting it all together (CSMA/CD)

Algorithm for sending data including:

Carrier Sense…
The node “listens” to the carrier medium to
see if anyone is transmitting
If another node is transmitting, wait until it
has finished
CSMA/CD (2)

Multiple Access
 many nodes are connected to the same carrier
medium

Collision Detection
 Each node listens during transmission
 If a collision is detected during transmission, both
transmitting nodes stop transmitting retry after a
random wait
 If collisions continue to occur, nodes extend their
wait time
Full Ethernet model




With good design, this method can deliver
90% efficiency of bandwidth
Main advantage is that time is not wasted in
transmitting whole packets when a collision
occurs
Most bus networks use CSMA/CD
Collisions can still cause problems if too
many workstations are connected to a single
network segment
 no means of prioritising
Collision animation
from http://handsonhowto.com/lan102.html
Transmitter B
Transmitter A

Why isn’t this a very good representation of a
collision in an Ethernet LAN?
Commercial Ethernet

Xerox formed an alliance with Digital and
Intel (DIX – Digital, Intel, Xerox))
DIX “Blue Book” Ethernet standard in
February 1980

Subsequently rewritten to the agreed
IEEE standards 802.x that
complemented the OSI model
Ethernet and OSI (1)

It was agreed that the Ethernet solution:
 must be addressed through the networking
software
 should fit into the lower layers of the OSI model


Standards set by the IEEE 802 committee
(802.3 – 1983 onwards) and D.I.X.
Encompasses OSI layers 1 & 2:
 an access method to the network
 a set of specifications with regard to cable and
data format (frames with MAC addresses)
Ethernet and OSI (2)
In 1982 original Blue Book standard
evolved into Ethernet II
 IEEE 802 model provides specifications
for:

physical network components, e.g. cable
layout of data within a packet, as “frames”
restrictions caused by network segments
IEEE 802.2 standard

Data Link Layer divided into two sublayers, to enable network interface cards
to talk to OSI layer 3 packets
Logical Link Control (LLC) sublayer
presents a uniform interface to the Network
layer
Media Access Control (MAC) sublayer
interfaces with the physical transmission
medium
IEEE 802 standards and
Access Methods
IEEE 802.3 CSMA/CD (Ethernet)
 IEEE 802.4 Token Bus networks

no longer used

IEEE 802.5 Token Ring networks
Still used in some legacy systems

IEE802.11 Wireless Networks
Peer-Peer and
Client-Server Networks
Lot of confusion…
 Refers to interactions between
processes

a “peer” computer could be being either
“client” or “server”
The other peer would then be “server” or
“client”
Peer-Peer and the Internet
Client/server
Process…
Server/client
Process…
network
Server A
Server B
Client-Server and LANs
Peer-peer: distributed resources
 LANs originally Ethernet & MAC
addresses

Client-server: centralisation of resources
» Microsoft networks… Domains
» Need domain controllers…
Routing with IP addresses
Packet switching…
 Data on screen divided into packets at
OSI layer 4…

OSI layer 3 packets
» each packet has source & destination
addresses in its header

Routing: two mechanisms
packets individually passed from router to
router towards destination
eventually arrive…
Larger Networks

Method 1: Routing Algorithm calculates
route through the network
all data between end points follow the
same route
Problems:
» massive waste of possible bandwidth
» can’t respond easily if new nodes added, or
nodes taken away

Method 2…
“packet switching”
Internet Routing
Uses IP protocol (OSI level 3)
 Each router:

reads the destination address of each
packet
decides what to do with the packet
» i.e. which other router to forward the packet to

Car hack via Internet…
https://www.youtube.com/watch?v=MK0SrxBC1xs
‘Store and Forward’ (1)
Packets arriving at a router may come
from several different connections
 May not arrive regularly

arrivals may be ‘bursty’

Router may not be able to process all
packets immediately on arrival
e.g. 2 packets arriving almost
simultaneously on different connections
‘Store and Forward’ (2)

Packets arrive at router…
 added to a “buffer”
» area of memory where data is stored temporarily until it
can be processed

Processed in order of arrival
 ‘first in, first out’ (FIFO)

Once buffer full, packets discarded and lost
Routing decisions

Router uses the destination IP address
in the packet IP header to decide what
to do with the packet
Maybe send to a local network to which the
router is connected
» router must know the IP addresses relevant to
its own local network(s)
Maybe forward on to another router
» which one?
Routing tables


Database of IP addresses (or parts of IP
addresses)
For each destination IP address
 link that a packet should be forwarded on

Router reads the destination IP address…
consults the routing table… forwards the
packet to the most appropriate next stage
Routing table
from
http://www.answers.com/to
pic/routing-protocol1?cat=technology
Construction of routing tables

Routing tables can be set up at any time…
 but network conditions may change
 a route that was once optimal may become
congested
 a link or router may malfunction or be removed
 a new link may be added to the network

Dynamic updates to routing tables absolutely
vital
Updating routing tables

Routers send each other information
about network conditions
broken links
new links
routers going off-line
congestion problems

Each router updates routing tables
accordingly
Normal route of packets
Router B
Recipient
Router C
Router A
Sender
Disaster strikes: link is broken
Router B
Recipient
Router C
Router A
Message cannot be delivered
Sender
What happens

Router A finds out about the broken link
no traffic received from router B
regular updates from router B don’t arrive

Router A knows enough about the local
network topology to use an alternative
route for packets…
routing table adjusted accordingly
Solution: a new route is found
Router B
Recipient
Router C
Router A
Sender
Decisions between multiple
possible routes

Factors to be considered by the router:
total number of ‘hops’ in the path
traffic loading on each hop
financial costs of using each hop

Algorithms for finding best routes:
Bellman-Ford (distance-vector algorithm)
Dijkstra (link-state algorithm)