Transcript routing algorithms

‫شبکه های‬
‫کامپیوتری پیشرفته‬
‫مطالب درس‬
‫‪ ‬مروری بر شبکه های کامپیوتری و اینترنت‬
‫‪ ‬شبکه های گسترده (‪)WAN‬‬
‫‪‬‬
‫‪ATM‬‬
‫‪MPLS ‬‬
‫‪ ‬شبکه های بی سیم‬
‫‪ ‬انتقال بی سیم‬
‫‪ ‬شبکه های بی سیم‬
‫‪ ‬شبکه های ‪MANET, WSN, WMN‬‬
‫‪ ‬شبکه های چندرسانه ای (‪)Multimedia‬‬
‫‪ ‬شبکه های نظیر به نظیر (‪)Peer-to-Peer‬‬
‫مروری بر شبکه های کامپیوتری و اینترنت‬
PC
server
wireless
laptop
cellular
handheld
millions of connected
computing devices:
hosts = end systems
 Mobile network
running network apps 
communication links 
fiber, copper, radio, 
access
satellite
points
wired transmission rate = 
bandwidth
links
router
Global ISP
Home network
Regional ISP
Institutional network
routers: forward packets 
(chunks of data)
4
A closer look at network structure:
network edge: applications and 
hosts
access networks, 
physical media:
wired, wireless
communication
links 
network core:
interconnected routers 
network of networks 
5
The network edge:
end systems (hosts): 
run application programs

e.g. Web, email

at “edge of network”

peer-peer
client/server model 
client host requests, receives 
service from always-on server
client/server
e.g. Web browser/server; 
email client/server
peer-peer model: 
minimal (or no) use of 
dedicated servers
e.g. Skype, BitTorrent 
6
Access networks and physical media
Q: How to connect end
systems to edge router?
residential access nets 
institutional access 
networks (school,
company): LAN
mobile access networks 
Keep in mind:
bandwidth (bits per 
second) of access
network?
shared or dedicated? 
7
Local area networks
company/univ local area
network (LAN) connects end
system to edge router
Ethernet:


10 Mbs, 100Mbps, 1Gbps, 10Gbps 
Ethernet
modern configuration: end systems 
connect into Ethernet switch
8
Wireless access networks
shared wireless access network
connects end system to router
via base station aka “access point”

router

wireless LANs: 
802.11b/g (WiFi): 11 or 54 Mbps

wider-area wireless access
provided by operators

~1Mbps over cellular system

WiMAX (10’s Mbps) over wide area

base
station

mobile
hosts
9
The Network Core
mesh of interconnected
routers

the fundamental question:
how is data transferred
through net?

circuit switching: dedicated circuit 
per call: telephone net
packet-switching: data sent thru 
net in discrete “chunks”
10
Internet protocol stack
application: supporting network
applications (FTP, SMTP, HTTP)
transport: process-process data
transfer (TCP, UDP)
network: routing of datagrams from
source to destination
IP, routing protocols



link: data transfer between
neighboring network elements
PPP, Ethernet



physical: bits “on the wire”

11
Encapsulation
source
message
segment
M
Ht
M
datagram Hn Ht
M
frame Hl Hn Ht
M
application
transport
network
link
physical
link
physical
switch
destination
M
Ht
M
Hn Ht
Hl Hn Ht
M
M
application
transport
network
link
physical
Hn Ht
Hl Hn Ht
M
M
network
link
physical
Hn Ht
M
router
12
error control (detection & recovery)
D
EDC= Error Detection and Correction bits (redundancy)
= Data protected by error checking, may include header fields
Error detection not 100% reliable!•
protocol may miss some errors, but rarely•
larger EDC field yields better detection and correction•
ARQ: automatic request repeat•
Stop and Wait•
Sliding Window•
13
Two Key Network-Layer Functions
forwarding: move packets from 
router’s input to appropriate router
output
routing: determine route taken by
packets from source to dest.

routing algorithms 
14
Interplay between routing and forwarding
routing algorithm
local forwarding table
header value output link
0100
0101
0111
1001
3
2
2
1
value in arriving
packet’s header
0111
1
3 2
15
Routing
Routing protocol
5
Goal: determine “good” path
(sequence of routers) thru
network from source to dest.
Graph abstraction for
routing algorithms:
graph nodes are routers

graph edges are
physical links

link cost: delay, $ cost,
or congestion level

2
A
B
2
1
D
3
C
3
1
5
F
1
2
E
“good” path: 
typically means minimum 
cost path
other def’s possible 
16
Routing: only two approaches used in
practice
Global:
all routers have complete topology, link cost info

“link state” algorithms: use Dijkstra’s algorithm to find
shortest path from given router to all destinations

Decentralized:
router knows physically-connected neighbors, link costs
to neighbors

iterative process of computation, exchange of info with
neighbors

“distance vector” algorithms

a ‘self-stabilizing algorithm’ (we’ll see these later)

17
Addressing: network layer
IP address: 32-bit
identifier for host,
router interface
interface: connection
between host, router
and physical link
router’s typically have
multiple interfaces

host may have multiple
interfaces

IP addresses associated
with interface, not
host, router


223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.2.9

223.1.1.3
223.1.3.27
223.1.2.2
223.1.3.2
223.1.3.1
223.1.1.1 = 11011111 00000001 00000001 00000001
223
1
1
18
1
IP Addressing
IP address:
network part (high
order bits)
host part (low order
bits)

223.1.1.1
223.1.2.1

223.1.1.2
223.1.1.4
223.1.2.9

what’s a network ?
(from IP address
perspective)
device interfaces with
same network part of IP
address

can physically reach
each other without
intervening router

223.1.1.3

223.1.3.27
223.1.2.2
LAN
223.1.3.1
223.1.3.2
network consisting of 3 IP networks
(for IP addresses starting with 223,
first 24 bits are network address)
19
LANs
bus topology popular through mid 90s 
today: star topology prevails 
active switch in center, each “spoke” runs a (separate) Ethernet protocol 
wireless LANS: 802.11 
bus: coaxial cable
switch
shared RF
(e.g., 802.11 WiFi)
star
20
LAN Addresses
Each adapter on LAN has unique LAN address (also has an IP address)
LAN (or MAC or physical) address:
used to get datagram from one 
interface to another physicallyconnected interface (same
network)
48 bit MAC address (for most 
LANs)
burned in the adapter ROM
Question: why separate
MAC and IP addresses?
21
ARP: Address Resolution Protocol
Question: how to determine
MAC address of B
knowing B’s IP address?
137.196.7.78
1A-2F-BB-76-09-AD
137.196.7.23
137.196.7.14
LAN
71-65-F7-2B-08-53
137.196.7.88
Each IP node (host,
router) on LAN has ARP
table

ARP table: IP/MAC
address mappings for
some LAN nodes

< IP address; MAC address; TTL>
TTL (Time To Live): time
after which address
58-23-D7-FA-20-B0mapping will be forgotten
(typically 20 min)

0C-C4-11-6F-E3-98
22
ARP protocol: Same LAN (network)
A wants to send datagram to 
B, and B’s MAC address not in
A’s ARP table.
A broadcasts ARP query  A caches (saves) IP-to-MAC 
address pair in its ARP table until
packet, containing B's IP
address information becomes old (times
out)
dest MAC address = FF-FF- 
soft state: information that 
FF-FF-FF-FF
times out (goes away) unless
all machines on LAN 
refreshed
receive ARP query
B receives ARP packet, replies  ARP is “plug-and-play”: 
to A with its (B's) MAC address
nodes create their ARP tables 
frame sent to A’s MAC  without intervention from
net administrator
address (unicast)
23
Addressing: routing to another LAN
walkthrough: send datagram from A to B via R
assume A knows B’s IP address
88-B2-2F-54-1A-0F
74-29-9C-E8-FF-55
A
111.111.111.111
E6-E9-00-17-BB-4B
1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
111.111.111.112
222.222.222.221
222.222.222.222
B
R
49-BD-D2-C7-56-2A
CC-49-DE-D0-AB-7D
two ARP tables in router R, one for each IP network
(LAN)

24
A creates IP datagram with source A, destination B 
A uses ARP to get R’s MAC address for 111.111.111.110 
A creates link-layer frame with R's MAC address as dest, frame 
contains A-to-B IP datagram
a really
important
A’sThis
NIC issends
frame

example – make sure you
R’s NIC receives frame

understand!
R removes IP datagram from Ethernet frame, sees its destined to 
B
R uses ARP to get B’s MAC address 
R creates frame containing A-to-B IP datagram sends to B 
88-B2-2F-54-1A-0F
74-29-9C-E8-FF-55
A
E6-E9-00-17-BB-4B
111.111.111.111
222.222.222.220
111.111.111.110
111.111.111.112
222.222.222.221
1A-23-F9-CD-06-9B
R
222.222.222.222
B
49-BD-D2-C7-56-2A
CC-49-DE-D0-AB-7D
25