Transcript Routing - La Salle University

WAN Technologies and Routing
Computer Networks and Internets
(Comer)
CSIT 220 (Blum)
1
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
CSIT 220 (Blum)
2
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).
CSIT 220 (Blum)
3
Bridges help
CSIT 220 (Blum)
4
Bridges Revisited
• 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.
CSIT 220 (Blum)
5
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).
CSIT 220 (Blum)
6
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.
CSIT 220 (Blum)
7
MAC addressing (random)
289
760
414
014
045
579
533
705
CSIT 220 (Blum)
774
301
709
814
8
Network addressing (logical)
101
201
301
202
302
102
103
104
CSIT 220 (Blum)
203
204
303
304
9
Hierarchical addressing
Name Desi Donnelly
Address 12 Park Range
Neighborhood Victoria Park
City Manchester M14 5HQ
Country UNITED KINGDOM
CSIT 220 (Blum)
10
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.
CSIT 220 (Blum)
11
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.
CSIT 220 (Blum)
12
ipconfig /all
Subnet mask 255.255.0.0
CSIT 220 (Blum)
13
Another Subnet mask
Subnet mask
CSIT 220 (Blum)
255.255.248.0
14
25511111111
CSIT 220 (Blum)
15
25511111111
CSIT 220 (Blum)
16
24811111000
CSIT 220 (Blum)
17
24811111000
CSIT 220 (Blum)
18
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.
CSIT 220 (Blum)
19
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
CSIT 220 (Blum)
20
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
CSIT 220 (Blum)
21
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.
CSIT 220 (Blum)
22
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.
CSIT 220 (Blum)
23
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.
CSIT 220 (Blum)
24
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.
CSIT 220 (Blum)
25
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.
CSIT 220 (Blum)
26
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.
CSIT 220 (Blum)
27
Fig. 13-6 (Comer)
CSIT 220 (Blum)
28
Fig. 13-6 (Comer)
CSIT 220 (Blum)
29
Packets don’t look back
• Next-hop switching has “source
independence” and more generally “history
independence.”
– The next-hop only depends on the packet’s
destination, not on where it started or where it’s
been.
• It makes the forwarding mechanism more
compact and efficient.
CSIT 220 (Blum)
30
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.
CSIT 220 (Blum)
31
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
CSIT 220 (Blum)
32
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
CSIT 220 (Blum)
33
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.
CSIT 220 (Blum)
34
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.
CSIT 220 (Blum)
35
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.
CSIT 220 (Blum)
36
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.
CSIT 220 (Blum)
37
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 220 (Blum)
38
Dijkstra’s algorithm
CSIT 220 (Blum)
39
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.
CSIT 220 (Blum)
40
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.
CSIT 220 (Blum)
41
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.
CSIT 220 (Blum)
42
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.
CSIT 220 (Blum)
43
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.
CSIT 220 (Blum)
44
Dijkstra Demo
CSIT 220 (Blum)
45
Dijkstra Demo (the root)
CSIT 220 (Blum)
46
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.
CSIT 220 (Blum)
47
Dijkstra Demo
CSIT 220 (Blum)
48
Dijkstra Demo
Ikeda is the cheapest at this stage.
CSIT 220 (Blum)
49
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.
CSIT 220 (Blum)
50
Dijkstra Demo
Ikeda connects to Takamatsu but the cost would be 131 = 74+
57 but we can already get to Takamatsu for cheaper than that.
CSIT 220 (Blum)
51
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.
CSIT 220 (Blum)
52
Dijkstra Demo
CSIT 220 (Blum)
Branch
with lowest
cost at this
stage
53
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.
CSIT 220 (Blum)
54
Dijkstra Demo
The cheapest active node is now Kawanoe.
CSIT 220 (Blum)
55
Dijkstra Demo
Kawanoe connects to Kochi for a cost of 187 = 100+87 but
we can already reach there for 156.
CSIT 220 (Blum)
56
Dijkstra Demo
The cheapest active node is now Muroto.
CSIT 220 (Blum)
57
Dijkstra Demo
Muroto connects to Kochi for a cost of 211=128+83 but we can
already reach there for a cost of 156.
CSIT 220 (Blum)
58
Dijkstra Demo
Kochi is now the cheapest active link.
CSIT 220 (Blum)
59
Dijkstra Demo
Kochi connects to Matsuyama for a cost of 283=156+127 but
Matsuyama can already be reached for a cost of 195.
CSIT 220 (Blum)
60
Dijkstra Demo
Matsuyama is now the cheapest active node.
CSIT 220 (Blum)
61
Dijkstra Demo
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.
CSIT 220 (Blum)
62
Dijkstra Demo
Nakamura is now the cheapest active node.
CSIT 220 (Blum)
63
Dijkstra Demo
Nakamura connects to Uwajima for a cost of 371=284+87
but Uwajima can already be reached for a cost of 287.
CSIT 220 (Blum)
64
Dijkstra Demo
Uwajima is now the cheapest active node.
CSIT 220 (Blum)
65
Dijkstra Demo
There are no more active nodes.
CSIT 220 (Blum)
66
Other References
• http://www-b2.is.tokushimau.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
• http://www.webopedia.com
• http://www.whatis.com
• http://www.networkcomputing.com/netdesi
gn/1122ipr.html (IP Routing Primer)
CSIT 220 (Blum)
67