Transcript Packet Forwarding

Advanced topics
in
Computer Networks
Lecture 4: Packet forwarding
University of Tehran
Dept. of EE and Computer Engineering
By:
Dr. Nasser Yazdani
Univ. of Tehran
Computer Network
1
Packet forwarding



How do routers process IP packets
How do they forward packets
Assigned reading

Section from “Computer Network: A System
Approach”
Univ. of Tehran
Computer Network
2
Forwarding vs. Routing

Forwarding: the process of moving packets
from input to output



The forwarding table Lookup.
How to populate the lookup table?
Routing: process by which the forwarding table
is built and maintained


One or more routing protocols
Procedures (algorithms) to convert routing into to
forwarding table.
Univ. of Tehran
Computer Network
3
Outline

Alternative methods for packet forwarding

IP packet routing
Univ. of Tehran
Computer Network
4
Techniques for Forwarding
Packets

Source routing


Table of virtual circuits



Packet carries path
Connection routed through network to setup
state
Packets forwarded using connection state
Table of global addresses (IP)


Routers keep next hop for destination
Packets carry destination address
Univ. of Tehran
Computer Network
5
Source Routing

List entire path in packet


Router processing, one option




Driving directions (north 3 hops, east, etc..)
Examine first step in directions
Strip first step from packet
Forward to step just stripped off
Or the address can be implemented by a
linked list in the packet header.
Univ. of Tehran
Computer Network
6
Source Routing Example
Packet
3,4,3
4,3
2
Sender
1
R1
2
3
R1
1
4
3
4
3
2
1
R2
4
Univ. of Tehran
Computer Network
3
Receiver
7
Source Routing

Advantages


Disadvantages



Switches can be very simple and fast
Variable (unbounded) header size
Sources must know or discover topology (e.g.,
failures)
Typical use


Machine room networks (Myprinet)
Debugging and management
Univ. of Tehran
Computer Network
8
Virtual Circuits/Tag Switching



Use the telephone model virtual circuits
Each flow is identified by a Virtual Circuits Identifier (VCI).
Connection setup phase, Signaling




Each packet carries connection ID


Use other means to route setup request
Each router allocates flow ID on local link
Creates mapping of inbound flow ID/port to outbound flow ID/port
Sent from source with 1st hop connection ID
Router processing



Lookup flow ID – simple table lookup
Replace flow ID with outgoing flow ID
Forward to output port
Univ. of Tehran
Computer Network
9
Virtual Circuits Examples
In-port
Lookup table for
Switch R1
Packet
5
In-VCI
Out-VCI
1
5
3
7
4
11
0
8
7
2
Sender
Out-port
1
R1
2
3
R2
1
4
1,7  4,2
3
4
1,5  3,7
2
2
1
R3
4
3
Receiver
6
2,2  3,6
Univ. of Tehran
Computer Network
10
Virtual Circuits

Advantages






Disadvantages



More efficient lookup (simple table lookup)
More flexible (different path for each flow)
Can reserve bandwidth at connection setup
Easier for hardware implementations
Small per-packet header overhead small.
Still need to route connection setup request
More complex failure recovery – must recreate
connection state
Typical uses


ATM – combined with fix sized cells
MPLS – tag switching for IP networks
Univ. of Tehran
Computer Network
11
IP Datagrams on Virtual
Circuits

Challenge – when to setup connections

At bootup time – permanent virtual circuits
(PVC)


For every packet transmission


Large number of circuits
Connection setup is expensive
For every connection


What is a connection?
How to route connectionless traffic?
Univ. of Tehran
Computer Network
12
IP Datagrams on Virtual
Circuits

Traffic pattern





Few long lived flows
Flow – set of data packets from source to
destination
Large percentage of packet traffic
Improving forwarding performance by using
virtual circuits for these flows
Other traffic uses normal IP forwarding
Univ. of Tehran
Computer Network
13
Datagram Switching





No connection setup phase since it is costly.
Each packet is forwarded independently
Sometimes called connectionless model
Analogy:
postal
system
Packet
Each switch
maintains a
forwarding
(routing)
table
R
R
2
Sender
1
R1
2
3
R1
1
4
R4
3
4
R3
R
2
1
R2
4
3
Receiver
R
R3
Univ. of Tehran
Computer Network
14
Datagram Model




There is no round trip time delay waiting for
connection setup; a host can send data as soon as it
is ready.
Source host has no way of knowing if the network is
capable of delivering a packet or if the destination
host is even up.
Since packets are treated independently, it is
possible to route around link and node failures.
Since every packet must carry the full address of the
destination, the overhead per packet is higher.
Univ. of Tehran
Computer Network
15
Global Addresses (IP)


Each packet has destination address
Each switch has forwarding table of
destination  next hop
At v and x: destination  east
 At w and y: destination  south
 At z: destination  north
Distributed routing algorithm for calculating
forwarding tables


Univ. of Tehran
Computer Network
16
Router Table Size

One entry for every host on the Internet


One entry for every LAN



100M entries, doubling every year
Every host on LAN shares prefix
Still too many, doubling every year
One entry for every organization


Every host in organization shares prefix
Requires careful address allocation
Univ. of Tehran
Computer Network
17
Outline

Alternative methods for packet forwarding

IP packet routing

Variable prefix match

Routing protocols – distance vector
Univ. of Tehran
Computer Network
18
Original IP Route Lookup

Address classes





A: 0 | 7 bit network | 24 bit host (16M each)
B: 10 | 14 bit network | 16 bit host (64K)
C: 110 | 21 bit network | 8 bit host (255)
We need to keep only network address,
221entries.
Address would specify prefix for
forwarding table

Simple lookup
Univ. of Tehran
Computer Network
19
Original IP Route Lookup –
Example

www.cmu.edu address 128.2.11.43




Forwarding table contains



Class B address – class + network is 128.2
Lookup 128.2 in forwarding table
Prefix – part of address that really matters
for routing
List of class+network entries
A few fixed prefix lengths (8/16/24)
Large tables

2 Million class C networks
Univ. of Tehran
Computer Network
20
CIDR Revisited

Supernets



Assign adjacent net addresses to same org
Classless routing (CIDR)
How does this help routing table?

Combine routing table entries whenever all
nodes with same prefix share same hop
Univ. of Tehran
Computer Network
21
CIDR Illustration
Provider is given 201.10.0.0/21
Provider
201.10.0.0/22
Univ. of Tehran
201.10.4.0/24
201.10.5.0/24
Computer Network
201.10.6.0/23
22
Classless Addressing
CIDR
Class-based:
0
A
B
C
D
232-1
• Class A cover a large range of addresses
Classless:
128.9.0.0
142.12/19
65/8
0
128.9/16
216
232-1
128.9.16.14
• Take part of address space for host addresses.
Univ. of Tehran
Computer Network
23
Classless Addressing
CIDR
128.9.19/24
128.9.25/24
128.9.16/20 128.9.176/20
128.9/16
0
232-1
128.9.16.14
Most specific route = “longest matching prefix”
Univ. of Tehran
Computer Network
24
IP Lookup


Packets are forwarded to their
destination based on their destination
addresses.
Router must find the address of the next
hop for each packet by finding the
longest prefix matching with the packet
destination address.
Univ. of Tehran
Computer Network
25
Forwarding Datagrams



“Network ID” uniquely identifies a physical
network.
All hosts and routers sharing a Network ID
share the same physical network.
Every network in Internet is connected to at
least one router that can exchange packets
with other routers
Univ. of Tehran
Computer Network
26
Forwarding Algorithm
If the datagram destination address is in the local
network
deliver packet over the interface
else if the network address is in the forwarding table
deliver packet to the corresponding next hop
else
deliver packet to the default router.


For Class address there is exact matching
For Classless address it is prefix matching.
Univ. of Tehran
Computer Network
27
Forwarding Table
128.17.20.1
R2
1
R1 2
3
R3
R4
128.17.16.1
e.g. 128.9.16.14 => Port 2
Prefix
Next-hop
Port
65/8
128.9/16
128.9.16/20
128.9.19/24
128.9.25/24
128.9.176/20
142.12/19
128.17.16.1
128.17.14.1
128.17.14.1
128.17.10.1
128.17.14.1
128.17.20.1
128.17.16.1
3
2
2
7
2
1
3
• It is prefix matching in the table.
Univ. of Tehran
Computer Network
28
Default Routing
R1
Default
Routing
R2
Univ. of Tehran
R3
Requires
Routing
Table
R4
Computer Network
R5
Default
Routing
29
Inside a Router
1.
Forwarding
Table
2.
3.
Output
Scheduling
Interconnect
Forwarding
Decision
Forwarding
Table
Forwarding
Decision
Forwarding
Table
Forwarding
Decision
Univ. of Tehran
Computer Network
30
Forwarding in an IP Router
A higher level view from router perspective.
• Lookup packet DA in forwarding table.
– If known, forward to correct port.
– If unknown, drop packet.
• Decrement TTL, update header Checksum.
• Forward packet to outgoing interface.
• Transmit packet onto link.
Univ. of Tehran
Computer Network
31
Global Addresses

Advantages


Stateless – simple error recovery
Disadvantages

Every switch knows about every destination


Potentially large tables
All packets to destination do not take same
route
Univ. of Tehran
Computer Network
32
Comparison
Source Routing
Global Addresses
Virtual Circuits
Header Size
Worst
OK – Large address
Best
Router Table Size
None
Number of networks
(prefixes)
Number of
circuits
Forward Overhead
Best
Prefix matching
Pretty Good
Setup Overhead
None
None
Connection Setup
Tell all routers
Tell all routers and
Tear down circuit
and re-route
Error Recovery
Univ. of Tehran
Tell all hosts
Computer Network
33
Next Lecture: Routers


How do you build a router
Assigned reading

[P+98] A 50 Gb/s IP Router
Univ. of Tehran
Computer Network
34