Network Design 16.583/483: University of Massachusetts Lowell

Network Design 16.
583/483 Spring 2010
University of Massachusetts Lowell
Network Design 16.583/483

Spring 2010
Class 5
Internetworking (2/2)
Prepared by: Dr. Hani Al-Dayaa ([email protected])
Lecture Outline
Routing Global Internet Multicast Multiprotocol Label Switching
Network Design 16.583/483 Spring 2010
Routing
Forwarding vs. Routing
Forwarding consists of taking a packet, looking at its destination address, consulting a table, and sending the packet in a direction determined by that table.
Simple well-defined process.
Routing is the process by which routing tables are built.

Complex distributed algorithms.
Network Num 18 Next Hop 171.69.245.10
A row from a Routing Table Network Num 18 Interface if0 MAC Address 8:2:2b:e4:b:1:2
A row from a Forwarding Table
Routing (contd)
Network as a Graph
The Nodes, A - F, may be hosts, switches, routers, or networks. Edges are network links. Each edge has an associated cost. Routing: Find the lowest-cost path between any two nodes.
Calculating all the shortest paths and loading them into a nonvolatile storage on each node is an option. What are the shortcomings of such a static approach?
It does not deal with node or link failures. It does not consider the addition of new nodes or links. It implied that edge costs cannot change, even though high cost can be temporarily assigned to a link that is heavily loaded.
Two main classes of routing protocols: Distance Vector and Link State. University of Massachusetts Lowell 4
Routing (contd)
Distance Vector
Each node constructs a vector containing the distances (costs) to all other nodes. It distributes that vector to its immediate neighbors. Each node knows the cost of the link to each of its directly connected neighbors. A link that is down is assigned an infinite cost.
Routing (contd)
Distance Vector (contd)
Initially, each node sets a cost of 1 to its directly connected neighbors and to all other nodes.
Initial distances stored at each node
Initial routing table at node A
Routing (contd)
The next step is that every node sends a message to its directly connected neighbors containing its personal list of distances. Update the routing table with costs and next hops for all nodes in the network.
Distance to Reach Node Information Stored at Node A B C D E A B C D E F G
0 1 1 2 1 1 2
1 0 1 2 2 2 3
1 1 0 1 2 2 2
2 2 1 0 3 2 1
1 2 2 3 0 2 3
1 2 2 2 2 0 1
2 3 2 1 3 1 0
Final routing table at node A
F G
Final distances stored at each node

Network Design 16.583/483 Spring 2010 University of Massachusetts Lowell 7
Routing (contd)
Directly connected neighbors exchange updates
Periodic Update: Each node automatically sends an update message
every so often, even if nothing has changed.
Triggered Update: It happens whenever a node receives an update from

one of its neighbors that causes it to change one of the routes in its routing table.
Each update is a list of pairs, (Destination, Cost).
Refresh existing routes, delete if they time out. Convergence: The process of getting consistent routing information to all
the nodes.
Check for failing links/nodes

Continually test the links by sending control packets. Wait for periodic hello (I am alive) messages.
In case of failure
Set the cost of reaching failed route to . Send update message. Network Design Spring 2010 16.583/483 Recreate the routing table.University of Massachusetts Lowell
Routing (contd)
Example of Routing Loops
F detects that link to G has failed. F sets distance to G to infinity and sends update to A. A sets distance to G to infinity since it uses F to reach G. A receives periodic update from C with 2-hop path to G. A sets distance to G to 3 and sends update to F. F decides it can reach G in 4 hops via A.
Routing (contd)
Routing Information Protocol (RIP)
Distributed with the BSD (Berkeley Software Distribution) version of Unix. Canonical example of distance vector based routing protocol The goal of routers is to know how to forward packets to various networks. Advertise cost of reaching networks not routers. Example
Router C would advertise to router A the fact that can reach networks 2 and 3 at a cost of 0, networks 5 and 6 at cost 1, and network 4 at cost 2.
10
Routing (contd)
Distance Vector
(contd)
Routing Information Protocol (RIP) (contd)

RIP packet format: Most of packet is (networks-address, distance) pairs. Routers running RIP run their advertisement every 30 seconds. Triggered Update: A router sends an update message whenever an
update from another router causes it to change its routing table.
It always tries to find a Minimum Hop Route Valid distances are 1 to 15, with 16 representing (infinity).
11
Routing (contd)
Source: Cisco Systems
12
Routing (contd)
13
Routing (contd)
Link State
Strategy
All nodes know their link costs to directly connected neighbors. Disseminate this information to the whole network. Then, every node has a complete map of the whole network. Find the shortest path to the destination. Two Mechanisms
Reliable dissemination of the link state information Route calculation from the accumulated link-state knowledge
Reliable Flooding
Make sure every node gets link-state information from every other node in the network Link State Packet (LSP)
ID of the node that created the LSP Cost of link to each directly connected neighbor Sequence Number (SEQNO) Time-To-Live (TTL) for this packet
University of Massachusetts Lowell 14
Routing (contd)
Link State (contd)
Reliable Flooding (contd)
Store most recent LSP from each node Forward LSP to all nodes but the one that sent it Generate new LSP periodically or triggered by link state change
Increment SEQNO (large SEQNO space 64 bits) Keep the period large (order of hours)
If periodic hello messages are not received from a neighbor then considered dead Start SEQNO at 0 when reboot Decrement TTL of each stored LSP
Discard when TTL = 0
Flooding of link-state packets. (a) LSP arrives at node X; (b) X floods LSP to A and C; (c) A and C flood LSP to B (but not Network Design 16.583/483 Spring 2010 X); (d) flooding is complete. University of Massachusetts Lowell
15
Routing (contd)
Link State
(contd)
Route Calculation: Dijkstras shortest path algorithm (also called Forward

Search algorithm) Algorithm (Theoric)
Let: N denotes set of nodes in the graph; l (i, j) denotes non-negative cost (weight) for edge (i, j); s denotes this node, M denotes the set of nodes incorporated so far by the algorithm; and C(n) denotes the cost of path from s to each node n.
// Start with M containing the node s.
M = {s}
// Initialize the table of costs to other nodes using the known costs to directly connected nodes.
for each n in N - {s} C(n) = l(s, n)

// Repeat until all nodes are incorporated in M.
while (N != M)
// Look at the node that is reachable at lowest cost (w) and add it to M.
M = M U {w} such that C(w) is the minimum for all w in (N - M)

// Update the table of costs by considering the cost of reaching nodes through w.
for each n in (N - M)
// Choose a new route to node n that goes through node w if the total cost of going // from the source to w and then following the link from w to n is less than the old route // we had to n. Network Design 16.583/483 Spring 2010
University of Massachusetts Lowell C(n) = MIN(C(n), C (w) + l(w, n ))
16
Routing (contd)
Link State
(contd)
Route Calculation: Dijkstras shortest path algorithm (also called Forward

Search algorithm) (contd) Algorithm (Practical)
1. Initialize the Confirmed list with an entry for myself: this entry has a cost of 0. 2. For the node just added to the Confirmed list in the previous step, call it node Next, select its LSP. 3. For each neighbor (Neighbor) of Next, calculate the cost (Cost) to reach this Neighbor as the sum of the cost from myself to Next and from Next to Neighbor. a. If Neighbor is currently not on either the Confirmed or the Tentative list, then add (Neighbor, Cost, NextHop) to the Tentative list, where NextHop is the direction I go to reach Next. b. If Neighbor is currently on the Tentative list, and the Cost is less than the currently listed cost for Neighbor, then replace the current entry with (Neighbor, Cost, NextHop), where NextHop is the direction I go to reach Next. 4. If the Tentative list is empty, stop. Otherwise, pick the entry from the Tentative list with the lowest cost, move it to the Confirmed list, and return to step 2.
Routing (contd)
Link State
(contd)
Route Calculation: Dijkstras shortest path algorithm (contd) Note: Also called Forward
Search algorithm
Steps for building routing table for node D

Routing (contd)
Link State
(contd)
Open Shortest Path First Protocol (OSPF)

Authentication of routing messages
To prevent misconfigured routers to cause a collapse. A router decides that it can reach every other host at a cost of 0.
Additional hierarchy
Further division of domains in areas.
Load balancing
Multiple routes to the same destination.
Currently set to 2 The sender of the message Checksum as in IP header Password or Cryptography Checksum Network Design 16.583/483 Spring 2010 1 = Hello (router is still alive) 2 = Database Description 3 = Link State Request 4 = Link State Update 5 = Link State Acknowledgment Packet length in bytes (including header) Identifier of the area in which the node is located 0 = No Auth 1 = Auth: Password 19 2 = Auth: Cryptography Checksum
OSPF Header Format

Routing (contd)
Link State (contd)
Metrics: How to assign costs to links?
Original ARPANET Metric
Measures number of packets queued on each link Took neither latency or bandwidth into consideration
2nd ARPANET Metric

Stamp each incoming packet with its arrival time (AT) Record departure time (DT) When link-level ACK arrives, compute Delay = (DT - AT) + Transmit + Latency If timeout, reset DT to departure time for retransmission Link cost = average delay over some time period
3rd ARPANET Metric (Fine Tuning)

Compress the dynamic range of the metric Replace Delay with link utilization
20
Routing (contd)
Routing for Mobile Hosts (Mobile IP)
Mobility Support: What happens when a destined host disconnects
from the network and connects to another by the time the router on the original network tries to deliver the packet to that host? Home Agent: This router is located on the Home Network of the Mobile
Host. The Mobile Host has a permanent IP address, called its Home Address, which has a network number equal to that of the Home Network, and thus of the Home Agent. Foreign Agent: It is located on a network to which the Mobile Host attaches itself when it is away from its Home Network.
Home and Foreign Agents periodically exchange advertisement messages. Care-of-Address: When the Mobile Host attaches to a Foreign Network, it
registers with the Foreign Agent it detects, providing the address of its Home Agent. The Foreign Agent then contacts the Home Agent, providing a Care-of-Address, usually the IP address of the Foreign Agent.
Any host trying to send a packet to the Mobile Host will send it with a destination address equal to the Home Address of that node.
21
Global Internet (contd)

The Tree Structure of the Internet Structure in 1990!
Todays Multibackbone Internet
22

Subnetting
Solve the problem of assigning 1 network number per physical network.
A class B network with slightly more than 255 hosts wastes over 64,000 addresses.
Subnets: Take a single IP network number and allocate the IP addresses

with that network number to several physical networks, called subnets.
Subnet Mask: It introduces another level of hierarchy into the IP address.

It defines the variable partition of host part.
Subnetting means that a host is now configured with both an IP address and a Subnet Mask for the Subnet to which it is attached.
23

Subnetting (contd)
An example of Subnetting
Example of forwarding table with subnetting for Router R1


Classless Routing (Supernetting)
Called CIDR: Classless Inter-Domain Routing Route aggregation: Use a single entry in a forwarding table to tell how to
reach a lot of different networks. CIDR requires placing /X after the prefix where X is the prefix length in bits. Example: The 20-bit prefix (11000000 00000100 0001) for all networks
192.4.16 through 192.4.31 is represented by 192.4.16/20.
The network numbers are represented in (length, value) pairs. All routers must understand CIDR addressing.
25

Interdomain Routing
Autonomous System (AS)
The Internet is orgnanized as ASs.
Exterior Gateway Protocol (EGP)

Concerned with reachability not optimal routes. EGP forced the tree-like topology onto the Internet. Topology could not become more general.
Border Gateway Protocol (BGP)

Replacement of EGP. Internet is arbitrarily interconnected set of ASs. General model to accommodate non-tree structured networks.
26

Interdomain Routing (contd)
Multiple backbone networks: Usually called Service Provider Networks.
Operated by private companies rather than the government. Sites are connected to each other in arbitrary ways.
Todays Multibackbone Internet

Multihomed Autonomous System Transit Autonomous System
Stub Autonomous System


IP Version 6 (IPv6)
128-bit Address (as opposed to 32 bits in IPv4) Autoconfiguration: The ability of hosts to automatically configure
themselves with such information as their own IP address and domain name.
Advanced Routing Capabilities: Including support for mobile hosts. Extension Headers: In the NextHeader field
Fragmentation Authentication and Security
28

IP Version 6 (IPv6) (contd)
IPv6 Packet Header
For QoS TTL
IPv6 Fragmentation Extension Header
29
Multicast
One-to-Many
Internet TV, information update (stock market info)
Many-to-Many
Multimedia teleconferencing, online multiplayer gaming, distributed computing
Normal IP communication is Unicast Multiple Unicasts to achieve Multicasting

Requires more bandwidth More traffic load around the source node Keep track of IP addresses of hosts in the Multicast group
Internet radio station with coming and going audience
Multicast address
Associated with an abstract group IPv4 -> 28 bits of possible Multicast addresses
30
Multicast (contd)
Source Specific Multicast (SSM)
Suitable for internet radio
Any Source Multicast (ASM)

Many-to-Many Multicast
Administer the membership in a Multicast group (leave, join, etc.)

IPv4 -> IGMP (Internet Group management Protocol) IPv6 -> MLD (Multicast Listener Discovery)
Multicast routing
Multicast forwarding table
Specifies a tree (rather than a path such as in Unicast routing)
31
Multiprotocol Label Switching (MPLS)

Overview
The router allocates a Label for each prefix in its routing table and advertise both the label and the prefix that it represents to its neighboring routers.
This advertisement is carried in the Label Distribution Protocol.
32
For Next Class

Solve Chapter 4 Exercises: 15, 19, and 28. Review Chapters 1 4 and prepare for Exam 1 that will take place next class.
33

Network Design 16.583/483: University of Massachusetts Lowell

Uploaded by

Copyright:

Available Formats

Network Design 16.583/483: University of Massachusetts Lowell

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Network Design 16.583/483: University of Massachusetts Lowell

Uploaded by

Copyright:

Available Formats

Network Design 16.

583/483 Spring 2010

University of Massachusetts Lowell