Routing and Forwarding Simulation on Paper

We will simulate:

Hop by hop forwarding

DV - Distance vector routing (like RIP)

LS - Link State routing (like OSPF)

“Ping” - Echo request, echo reply, unreachable.

Topology

Each group knows about their own connections to other groups

Groups do not know about connections between other groups

Every group gets a different diagram, showing the connections that they know about, but not showing the connections that they do not know about.

Hop by hop forwarding

Forwarding table lists destinations and corresponding next-hop

Where does forwarding table come from?

Messages have source address, destination address, and a message body

If destination is yourself, read message and respond

If not addressed to you, decrement TTL and pass message on to next hop

Discard message if destination is unknown

Central Clocking

You will be told:

When to prepare updates to send to neighbours

When to send updates to neighbours

When to update your routing table with information received from neighbours.

Please do not send any routing messages at any other times.

Real routing protocols do not use central clocking. This is just an exercise.

Distance Vector Routing Simulation

RIP is a distance vector protocol. This exercise is a much simplified version.

Instructors pass out information about topology.

Each group knows about their direct neighbours, but not distant destinations.

Protocol will “learn” how to get to distant destinations.

DV Simulation - Create a distance vector routing table

Create a distance vector table showing routes to all destinations that you know about.

Table will contain three columns:

Destination (A, B, C, ...)

Cost (0 for yourself, 1 for your direct neighbours, more for distant destinations)

Next hop (yourself or a direct neighbour, never anything more distant)

Table will contain one row for each destination you know about.

DV Simulation - Your routing table

For example, if you start with:

Your location = K

Your neighbours = W and X

You do not yet know anything else

Then your routing table looks like this:

Make your own table now

Destination

Distance

Next Hop

K

0

(self)

W

1

W

X

1

X

DV Simulation – Prepare to send copies to neighbours

Make copies of your distance vector table

but leave out the next hop. Just include the destination and cost

You need one copy for each neighbour

Make copies now, but do not send them to neighbours yet

DV Simulation - What the copy looks like

For example, if your DV table looked like this:

Then the copy should look like this:

Destination

Distance

K

0

W

1

X

1

Distance (from you to destination)

(Your own routing table contains “Next Hop” information, but you DO NOT send your “Next Hop” information to your neighbours.)

Destination

Distance

Next Hop

K

0

(self)

W

1

W

X

1

X

DV Simulation – Exchange copies of DV table with neighbours

Wait for instructors to tell you to go.

Take the copies you made, and give them to each of your neighbours

Expect to receive a copy of the distance table from each of your neighbours

DV Simulation - What your neighbour (W) sends to you

Your location: K

For example, you receive this from one of your neighbours (W)

Destination

Distance (from neighbour to destination)

W

0

K

1

Q

1

(you do not receive neighbour’s Next Hop information)

DV Simulation - What your neighbour (X) sends to you

Your location: K

For example, you receive this from another neighbour (X)

Distance (from neighbour to destination)

Destination

X

0

P

1

W

1

(you do not receive neighbour’s Next Hop information)

DV Simulation - Update table using new information from neighbours

Add 1 to the cost of everything your neighbours told you

If there are any destinations that you did not have before, add them to your table

next hop is the neighbour that told you about the new destination

If your neighbour can get to a destination for lower cost than you had before, update your table to show new cost and next hop

DV Simulation - What you learn from what your neighbour (W) sent

Your location: K

Add 1 to costs from your neighbour (W)

Note any new or better routes

Destination

Distance

W

0+1 = 1

K

1+1 = 2

Q

1+1 = 2

Next Hop is your neighbour

W

W

W

This is new, so add it to your table.

Distance is worse than before; DO NOT change your table.

This is the same as before

DV Simulation - Your new routing table after update from W

Your location: K

Your neighbours: W and X

Update your routing table after neighbour W sent you an update

Destination

Distance

Next Hop

K

0

(self)

W

1

W

X

1

X

Q

2

W

This is new

DV Simulation - What you learn from what your neighbour (X) sent

Your location: K

Add 1 to costs from your neighbour (X)

Note any new or better routes

Destination

Distance

X

0+1 = 1

P

1+1 = 2

W

1+1 = 2

Next Hop is your neighbour

X

X

X

This is worse than before

This is new

This is the same as before

DV Simulation - Your new routing table after update from X

Your location: K

Your neighbours: W and X

Update your routing table after neighbour X sent you an update

Destination

Distance

Next Hop

K

0

(self)

W

1

W

X

1

X

Q

2

W

This came from W

P

2

X

This is new after update from X

DV Simulation - Repeat

Once per minute, send a copy of your table to each neighbour

Keep track of times when neighbours send data to you

If 4 minutes pass with no update, neighbour is dead

Delete table entries that have dead neighbour as next hop

DV Simulation – Differences from reality

Real DV protocols can detect dead peers

Real DV protocols can delete routes

Many other differences.

Link State Simulation

Forget everything about the topology from the previous exercise

Instructors pass out new information about topology

Each group knows about their direct neighbours, but not distant groups

LS Simulation - Create a link state table

Create a link state table showing all links that you know about

Table will contain:

Link identification (A to B, F to H, …)

Diagram shows your links

Cost of link (any integer)

Choose your own costs for direct links and write them on your diagram

Both directions have a cost, and they might be different. “A to B” is not the same as “B to A”.

LS Simulation - Your link state table

Your location: K

Your neighbours: W and X

Link from/to

Link Cost

K to W

12

K to X

32

LS Simulation - Your shortest-path table

Your location: K

Your neighbours: W and X

Destination

Total Cost

Shortest Path

K

0

K (self)

W

12

K - W

X

32

K - X

LS Simulation - Send copies to neighbours

Make copies of your link state table

Give a copy to each of your neighbours

Expect to receive a copy of the link state table from each of your neighbours

Send exact copies, don’t leave anything out

LS Simulation - What you send to your neighbours

Your location: K

Send this to your neighbours (W and X)

Link from/to

Link Cost

K to W

12

K to X

32

LS Simulation - What your neighbour sends to you

Your location: K

You receive this from your neighbour (W)

Link from/to

W to X

3

W to Q

6

W to K

10

Link Cost (for using this link in this direction)

LS Simulation - Update link-state table

Merge the link states that your neighbours send you with those you already have

LS Simulation - Your new link-state table after update

Your location: K

Your neighbours: W and X

Update your link state table after neighbour W sent you an update

Link Cost (for using this link in this direction)

Link from/to

K to W

12

K to X

32

W to X

3

W to Q

6

W to K

10

LS Simulation - Use link-state table to update diagram

Your link-state table tells you about all the links you know about.

Different directions are treated like different links. “A to B” is not the same as “B to A”.

Your network diagram contains exactly the same information, just in a different format.

Update the diagram using the table.

LS Simulation - Use link-state table to make shortest-path table

Your link-state table or your network diagram tells you about all the links you know about.

Different directions are treated like different links. “A to B” is not the same as “B to A”.

There will often be several ways to get to a destination. Choose the path with the lowest total cost. Use the diagram to help you.

Make a table showing all destinations, how to get there, total cost.

LS Simulation - Your new shortest-path table after update

Your location: K

Your neighbours: W and X

Destination

Total Cost

Shortest Path (how to get to destination)

K

0

K (self)

W

12

K - W

X

12+3 = 15

K - W - X

Q

12+6 =18

K - W - Q

This is better than K-X

LS Simulation - Repeat

Whenever anything changes, send a copy of the changes to each neighbour

changes can be new links, changes in cost, or deleted links (link failure or death of peer)

Also update all your tables and diagrams whenever anything changes.

In reality, OSPF does not re-send information that it has already sent to that neighbour

In this exercise, re-send a complete copy of your link state table

Your location: K

Send a complete copy of your link state table

Do not send your next-hop forwarding table

LS Simulation - What you send to your neighbours (update)

Link Cost (for using this link in this direction)

Link from/to

K to W

12

K to X

32

W to X

3

W to Q

6

W to K

10

Real LS protocols send only the differences between one update and the next, they do not send entire copies of the state table.

Real LS protocols can detect dead peers and dead links.

Many other differences.

LS Simulation – Differences from reality

NOTE TO INSTRUCTORS

Instructors know the complete topology.

Students all get different diagrams, showing only their own direct neighbours, not showing more distant topology.

When printing these notes, remember that everything after this page needs special treatment.

From page 1 to just before this page, treat it like a normal presentation. That probably implies printing in 6-up layout, with one copy per student.

This page is not printed at all.

Each group of students will need about 10 copies of the DV and LS routing update messages, and 1 or 2 copies of the echo request, echo reply and unreachable message templates. You can make multiple copies of the same page in the powerpoint presentation and then print 6-up.

Each group of students will need 1 large copy of their own partial topology, and 1 or 2 large copies of the routing tables.

Instructors will need 1 or 2 large copies of the complete topology.

Distance Vector (DV) routing table
as known by ______

Time: ___________

Destination	Total Cost Next Hop

Instructions: Start with yourself and your neighbours. When you get updates from neighbours, update this table.

Time: ___________

Link from/to	Link Cost

(LS) Table of Link States
as known by ______

Instructions:

1. Start by filling in costs of all directly-connected links.

2. When you get updates from neighbours, update this table.

(LS) Shortest-Path Table derived from Link State Table as known by ______

Time: ___________

Destination	Total Cost Shortest Path

Instructions: Use your link-state table to figure out the shortest path to each destination. Update this shortest-path table when something changes.

Message From ______ to ______
Type: DV routing update

Time: ___________

Destination	Total Cost

Instructions for Sender:

1. Fill in source, destination, time.

2. Copy your DV routing table, but leave out the “Next Hop” column.

3. Send to your neighbour.

Instructions for Receiver:

1. Add 1 to all costs.

2. If there are any costs lower than before, update cost and Next Hop in your table.

3. Similarly for any new destinations.

Message From ______ to ______
Type: DV routing update

Time: ___________

Destination	Total Cost

Instructions for Sender:

1. Fill in source, destination, time.

2. Copy your DV routing table, but leave out the “Next Hop” column.

3. Send to your neighbour.

Instructions for Receiver:

1. Add 1 to all costs.

2. If there are any costs lower than before, update cost and Next Hop in your table.

3. Similarly for any new destinations.

Message From ______ to ______
Type: DV routing update

Time: ___________

Destination	Total Cost

Instructions for Sender:

1. Fill in source, destination, time.

2. Copy your DV routing table, but leave out the “Next Hop” column.

3. Send to your neighbour.

Instructions for Receiver:

1. Add 1 to all costs.

2. If there are any costs lower than before, update cost and Next Hop in your table.

3. Similarly for any new destinations.

Message From ______ to ______
Type: LS routing update

Time: ___________

Link from/to Link Cost

Instructions for Sender:

1. Fill in source, destination, time.

2. Copy your LS routing table; do not leave out anything.

3. Send to your neighbour.

Instructions for Receiver:

1. If any costs have changed for links that you already knew, update your routing table.

3. Similarly for any new links.

Message From ______ to ______
Type: LS routing update

Time: ___________

Link from/to	Link Cost

Instructions for Sender:

1. Fill in source, destination, time.

2. Copy your LS routing table; do not leave out anything.

3. Send to your neighbour.

Instructions for Receiver:

1. If any costs have changed for links that you already knew, update your routing table.

3. Similarly for any new links.

Message From ______ to ______
Type: LS routing update

Time: ___________

Link from/to	Link Cost

Instructions for Sender:

1. Fill in source, destination, time.

2. Copy your LS routing table; do not leave out anything.

3. Send to your neighbour.

Instructions for Receiver:

1. If any costs have changed for links that you already knew, update your routing table.

3. Similarly for any new links.

Message From ______ to ______
Type: Echo Request

TTL: ______ Request ID: _________

Instructions for Original Sender:

1. Fill in source, destination, TTL, ID.

2. Consult your routing table to choose next hop.

3. Send to next hop.

Instructions for Receiver:

1. If message is addressed to you, send back Echo Reply.

2. If message is not addressed to you: Decrement TTL,

3. If TTL is zero, send back Error: TTL Exceeded.

4. Consult your routing table to choose next hop.

5. If destination is unknown, send back Error: Host Unreachable

6. Send message to next hop.

Message From ______ to ______
Type: Echo Request

TTL: ______ Request ID: _________

Instructions for Original Sender:

1. Fill in source, destination, TTL, ID.

2. Consult your routing table to choose next hop.

3. Send to next hop.

Instructions for Receiver:

1. If message is addressed to you, send back Echo Reply.

2. If message is not addressed to you: Decrement TTL,

3. If TTL is zero, send back Error: TTL Exceeded.

4. Consult your routing table to choose next hop.

5. If destination is unknown, send back Error: Host Unreachable

6. Send message to next hop.

Message From ______ to ______
Type: Echo Reply

TTL: ______ Original ID: _________

Instructions for Original Sender:

1. Fill in source, destination, TTL, Original ID (copied from request).

2. Consult your routing table to choose next hop.

3. Send to next hop.

Instructions for Receiver:

1. If message is addressed to you: You received a reply! Congratulations!

2. If message is not addressed to you: Decrement TTL,

3. If TTL is zero, discard packet. Do not send error message.

4. Consult your routing table to choose next hop.

5. If destination is unknown, discard packet. Do not send error message.

6. Send message to next hop.

Message From ______ to ______
Type: Echo Reply

TTL: ______ Original ID: _________

Instructions for Original Sender:

1. Fill in source, destination, TTL, Original ID (copied from request).

2. Consult your routing table to choose next hop.

3. Send to next hop.

Instructions for Receiver:

1. If message is addressed to you: You received a reply! Congratulations!

2. If message is not addressed to you: Decrement TTL,

3. If TTL is zero, discard packet. Do not send error message.

4. Consult your routing table to choose next hop.

5. If destination is unknown, discard packet. Do not send error message.

6. Send message to next hop.

Message From ______ to ______
Error Type: ______________

TTL: ______ Orig ID : ______Orig Dest : ______

Instructions for Original Sender:

1. Fill in source, destination, TTL, Original ID, Original Destination.

2. Consult your routing table to choose next hop.

3. Send to next hop.

Instructions for Receiver:

1. If message is addressed to you: There was an error! Sorry!

2. If message is not addressed to you: Decrement TTL,

3. If TTL is zero, discard packet. Do not send error message.

4. Consult your routing table to choose next hop.

5. If destination is unknown, discard packet. Do not send error message.

6. Send message to next hop.

Message From ______ to ______
Type: _____________

TTL: ______

Message:

Complete Topology
as known to instructors

IJ

GH

EF

CD

AB

Partial Topology
as known to group AB

IJ

EF

CD

AB

Partial Topology
as known to group CD

IJ

GH

CD

AB

Partial Topology
as known to group EF

GH

EF

AB

Partial Topology
as known to group GH

GH

EF

CD

Partial Topology
as known to group IJ

IJ

CD

AB

Afnog 2005 E2 - Routing simulation on paper

Originally by apb, for INET 2000 (Yokohama).
Updated for AfNOG 2001, 2002, 2003, 2004, 2005.

Afnog 2002 T2

2005-04-22T09:13:14