Transcript Routing - La Salle University

CSIT 320
(Blum)
WAN Technologies and Routing
Computer Networks and
Internets (Comer)
1
2
CSIT 320 (Blum)
Networks
 Networks
are grouped into (fuzzy)
categories based on the distances they
span and the number of nodes





HAN: Home Area Network
LAN: Local Area Network
CAN: Campus Area Network
MAN: Metropolitan Area Network
WAN: Wide Area Network
3
CSIT 320 (Blum)
Scalability
 As
the number of nodes increases, issues of
scalability arise. For a network to “scale”

One should be able to add nodes easily.

The network’s functionality should remain relatively
constant when nodes are added.
 The
physical problems (attenuation &
interference) are more readily overcome than
the sharing problem (many nodes trying to
transmit on a shared connection).
4
Bridges help
CSIT 320 (Blum)
5
CSIT 320 (Blum)
Bridges

Bridges work at Layer 2

Bridges help reduce traffic because a bridge
“learns” whether it filters or forwards a frame.

Unicast messages do not have to be
forwarded to all segments but only to those
connecting the source and destination.

This allows different segments to transmit
different signals simultaneously (in parallel)
giving the network scalability.
6
CSIT 320 (Blum)
Router
A
router serves a very similar purpose

It separates traffic into local (network) traffic and
(internet) traffic that must be sent on.

It sends the latter in the right general direction.
 Routers
and bridges work in different layers:

A bridge operates at the Data Link Layer using MAC
addresses (hardware addresses).

A router operates at the Network Layer using
network addresses (software addresses, e.g. IP
addresses).
7
CSIT 320 (Blum)
That’s Illogical
 Bridges
use the MAC address.
 The
problem with MAC addresses is that they are
essentially distributed at random over the
network.

Two nearby computers can have very different
MAC addresses.
 Recall
that first part of the MAC address is associated
with the manufacturer.

Computers with consecutive MAC addresses
could be many thousands of miles apart.
8
CSIT 320 (Blum)
MAC addressing (random)
289
760
414
014
045
579
533
705
774
301
709
814
9
CSIT 320 (Blum)
Network addressing (logical)
101
201
301
202
302
102
103
104
203
204
303
304
10
Hierarchical addressing
Name Desi Donnelly
Address 12 Park Range
Neighborhood Victoria Park
City Manchester M14 5HQ
Country UNITED KINGDOM
CSIT 320 (Blum)
11
CSIT 320 (Blum)
Hierarchical addressing
(Cont.)
 The
postal service reads the previous
address starting from the bottom.
 There’s
no need to read past United
Kingdom until the letter reaches the UK.
 There’s
no need to read past Manchester
until the letter reaches Manchester.
 And
so on.
12
CSIT 320 (Blum)
Hierarchy of IP
 An
IP address has a somewhat similar hierarchy.
 An
IP address is divided into two parts:

The first part specifies a particular network (a
neighborhood of nearby computers).

The second part specifies a particular node.
 There’s
no sense looking at the second part (the
node) until you have a match on the first part
(the network).
 The
subnet mask provides the dividing line
between the network and node portions of the
address.
13
ipconfig /all
Subnet mask 255.255.0.0
CSIT 320 (Blum)
14
Another Subnet mask
Subnet mask
255.255.248.0
CSIT 320 (Blum)
15
25511111111
CSIT 320 (Blum)
16
25511111111
CSIT 320 (Blum)
17
24811111000
CSIT 320 (Blum)
18
24811111000
CSIT 320 (Blum)
19
CSIT 320 (Blum)
Subnet masks
 255.255.0.0

11111111.11111111.00000000.00000000
 255.255.248.0

11111111.11111111.11111000.00000000
 Subnet
masks usually have the property that in
binary they are a string of all 1’s followed by a
string of all 0’s.
20
CSIT 320 (Blum)
The subnet-mask division
 The
part of the IP address (expressed in
binary) that corresponds to the 1’s portion
of the subnet mask is the network portion.

1’s  network
 The
part of the IP address (expressed in
binary) that corresponds to the 0’s portion
of the subnet mask is the node portion.

0’s  node
21
CSIT 320 (Blum)
Example
 IP:
139.84.33.18 
10001011.01010100. 00100001. 00010010
 Subnet
mask: 255.255.248.0 
11111111.11111111.11111000.00000000
 Network
part: 
10001011. 01010100. 00100000. 00000000
 Node
part: 
00000000. 00000000. 00000001. 00010010
22
CSIT 320 (Blum)
Comparison
 IP
addressing is simpler because it is systematic.
A
MAC address consists of 48 bits and all of the
bits must be looked at by each and every
bridge.
 An
IP(v4) address consists of 32 bits and only the
first part must be looked at by a router until a
match is found and after that only the second
part must be considered.
23
CSIT 320 (Blum)
Router
A
router connects two or more networks to form
an internet.

Sometimes the router connects two or more subnetworks to form a network.
A
router may be a specific device or it may be
software on a computer.
A
router determines where to forward “internet”
traffic (messages whose source is on one
network and destination is on another network).
 It
also filters out local traffic.
24
CSIT 320 (Blum)
Designing a WAN
 Similar
to the ideas of dividing a network into
“bridged” segments,

an internet can be divided into “routed” networks.

Or a network can be divided into “routed”
subnetworks.
 Ideally
one should study the usage (traffic
patterns) and place routers in such a way that
filtering is efficient.
25
CSIT 320 (Blum)
Store and Forward

The network is designed so that many signals are being
transmitted simultaneously (in parallel), thus several
packets may reach a router in very rapid succession.

This feature of packet switching is handled by the STORE
and FORWARD paradigm.

Packets are queued up as they arrive (“stored”) and then
sent on their way (“forwarded”) when the processor
catches up.

If the queue is full, the packet is dropped and the router
may or may not send a message indicating as much.
26
CSIT 320 (Blum)
Hop
A
hop is the transmission of a packet from one
router (or other intermediate point) to another.
 In
TCP/IP protocol, the number of hops a packet
is allowed to make is kept in the packet header
(in the TTL time-to-live field). Each router reduces
the number by one. When the TTL reaches 0, the
packet is discarded.

This is another difference between a bridge and a
router: a router can make (small) changes to the
packet.
27
CSIT 320 (Blum)
Next-Hop Forwarding
A
router has information about the next
place (hop) to forward the packet so that
it will eventually reach its destination.
 The
next-hop information is put into a
table (called a routing table).

It tells the packet which interface to use as
it passes through the router.
28
Fig. 13-6 (Comer)
CSIT 320 (Blum)
29
Fig. 13-6 (Comer)
CSIT 320 (Blum)
30
CSIT 320 (Blum)
Packets don’t look back
 Next-hop
switching has “source
independence” and more generally
“history independence.”

 It
The next-hop only depends on the packet’s
destination, not on where it started or
where it’s been.
makes the forwarding mechanism more
compact and efficient.
31
CSIT 320 (Blum)
Routing
 All
destination addresses with the same first part
will be forwarded (routed) to the same packet
switch.

That’s not exactly true. A given network
destination (as opposed to node destination) may
be listed on the table a few times.

This allows the router to “re-route” packets if
previous packets have not gotten through, in case
a connection goes down or is jammed with traffic.
32
CSIT 320 (Blum)
Routing
 Using
only this first part of the address (the
network portion) to route the packet
results in

A shorter table: an entry per network as
opposed to an entry per computer

A shorter computation time for routing as
the table is shorter and better organized
 think
of searching a sorted array versus
searching an unsorted array
33
CSIT 320 (Blum)
Interior/Exterior

Some routers do not connect to a network
(group of end-user computers) but only to
other routers or gateways. They are said to
be “interior.”

Those connected to computers are called
“exterior.”

Analogy: interior gateways are like two major
highways meeting without any cities nearby
34
CSIT 320 (Blum)
The best of all possible routes
 Routing
tables should have an entry for
each possible destination, this is called
Universal Routing.
 Routing
tables should have the “shortest”
path for the destinations, this is called
Optimal Routing.
35
CSIT 320 (Blum)
Default Routes

One way to deal with the competing needs
of having a hop for each destination and
having small tables is to use default routes.

It’s analogous to the default case in a switch
statement, any case not explicitly found
elsewhere in the table follows the default hop.

If one hop is very popular, making it the
default shortens the table.
36
CSIT 320 (Blum)
Routing Table Computation
 Static
Routing

A program computes and installs a packet
switch when it boots and the routes do not
change.

Routing is simplistic and low network
overhead, but the routing is inflexible.
37
CSIT 320 (Blum)
Routing Table Computation
 Dynamic

A program builds an initial routing table when
router boots and alters the table as the conditions
in the network change.

The network can handle problems automatically.

Used by most large networks. They are designed
with redundant hardware to handle the
occasional failures. The dynamic computation
allows the network to recover easily.
38
CSIT 320 (Blum)
Bridges/Routers
 Recall
that bridges could not be used
simultaneously if there was a loop.
 Routers
can have loops and remain
active; they are more “intelligent” and
can avoid the “infinite loop” problem.
A
connection does not have to be down
for a router to reroute packets, heavy
traffic may be enough.
CSIT 320
(Blum)
Dijkstra’s algorithm
39
40
CSIT 320 (Blum)
Building a routing table
 Each
router sends packets to the routers it
connects to (its “nearest neighbors”).
 From
the responses to these packets, the router
gathers information on the “cost” to transmit to
each neighbor.

Cost is based on bandwidth, traffic, etc.
 This
information is compiled into the “link state
packet” (LSP).
 The
LSP is transmitted to the neighbors and
beyond.
41
CSIT 320 (Blum)
Building a routing table (Cont.)
 The
router now has information on

all of the nodes in the networks

the links connecting them

the cost thereof
 The
router wants to find the least costly
path to all of the other nodes.
42
CSIT 320 (Blum)
Math terminology
 Abstractly,
the network is represented by
what mathematicians call a graph.
A
graph is made up of two sets

The vertices (our nodes)

The edges (our transmission lines) which
connect two vertices
A
graph is said to be “connected” if there
is at least one path along the edges
connecting every pair of vertices.
43
CSIT 320 (Blum)
Math terminology (Cont.)
A
graph is called “simply connected” if for
each pair of vertices, there is only one
path connecting them.

A simply connected graph has no loops.

A tree is a simply connected graph.
 Networks
are typically not simply
connected (they are not trees), so there is
often more than one path between
nodes.
44
CSIT 320 (Blum)
Dijkstra’s algorithm
 Dijkstra’s
algorithm is a way for a router to
select the least costly path to another
node (router).
 One
constructs a “tree” that spans the
graph.
 The
root of the tree is the router for which
we are building the table.
45
Dijkstra Demo
CSIT 320 (Blum)
46
CSIT 320 (Blum)
Dijkstra Demo (the root)
47
CSIT 320 (Blum)
Nearest Neighbors
 Next
one includes the branches to the
root’s nearest neighbors.
 One
selects the least costly one of these
to continue the procedure.
 This
is shown in red in the demo screen
captures.
48
Dijkstra Demo
CSIT 320 (Blum)
49
Dijkstra Demo
Ikeda is the cheapest at this stage.
CSIT 320 (Blum)
50
CSIT 320 (Blum)
Competing paths
 Examine
the nearest neighbors of that
least costly path.
 The
cost of a path is the sum of the costs
of the links connecting the source (root)
to a node.
 If
a path takes us to a node which already
has been reached, then we compare the
costs of the two paths and keep the
lower.
Dijkstra Demo
51
CSIT 320 (Blum)
Ikeda connects to Takamatsu but the cost would be 131 = 74+
57 but we can already get to Takamatsu for cheaper than that.
52
CSIT 320 (Blum)
No turning back
 Once
a node has been analyzed as the
least costly path, we are through with it.

That’s not to say it won’t be used as part of
the path of many other paths.

It only means we are through analyzing it.

These nodes are shown in blue in the demo
screen captures.
53
Dijkstra Demo
CSIT 320 (Blum)
Branch
with lowest
cost at this
stage
54
CSIT 320 (Blum)
Dijkstra Demo
Takamatsu connects to Kawanoe for a a cost of
149=76+73 but we can already get there for a cost of 100.
55
Dijkstra Demo
The cheapest active node is now Kawanoe.
CSIT 320 (Blum)
56
CSIT 320 (Blum)
Dijkstra Demo
Kawanoe connects to Kochi for a cost of 187 = 100+87 but
we can already reach there for 156.
57
Dijkstra Demo
The cheapest active node is now Muroto.
CSIT 320 (Blum)
58
CSIT 320 (Blum)
Dijkstra Demo
Muroto connects to Kochi for a cost of 211=128+83 but we can
already reach there for a cost of 156.
59
Dijkstra Demo
Kochi is now the cheapest active link.
CSIT 320 (Blum)
Dijkstra Demo
60
CSIT 320 (Blum)
Kochi connects to Matsuyama for a cost of 283=156+127 but
Matsuyama can already be reached for a cost of 195.
61
Dijkstra Demo
Matsuyama is now the cheapest active node.
CSIT 320 (Blum)
Dijkstra Demo
62
CSIT 320 (Blum)
Matsuyama connects to Uwajima for a cost of 287=195+92
beating the previous cost of 304, so we throw out the old path
and keep the new.
63
Dijkstra Demo
Nakamura is now the cheapest active node.
CSIT 320 (Blum)
64
CSIT 320 (Blum)
Dijkstra Demo
Nakamura connects to Uwajima for a cost of 371=284+87
but Uwajima can already be reached for a cost of 287.
65
Dijkstra Demo
Uwajima is now the cheapest active node.
CSIT 320 (Blum)
66
Dijkstra Demo
There are no more active nodes.
CSIT 320 (Blum)
67
CSIT 320 (Blum)
Other References
 http://www-b2.is.tokushima-
u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
 http://www.webopedia.com
 http://www.whatis.com
 http://www.networkcomputing.com/netd
esign/1122ipr.html (IP Routing Primer)