Transcript cross_ip - cs.wisc.edu

Switching, Internet Protocol
Outline
Quiz 2 Solution
Crossbar switch design
Knockout switch design
Introduction to Internet Protocol
PROJECT #2 DUE THURSDAY!!
Fall, 2001
CS 640
1
Quiz 2 Solution
a)
C
5
2
A
6
10
D
1
3
B
7
4
E
F
3
b) Routing table for A
M
B
C
D
E
F
{A}
2B
5C
10 D
Inf
Inf
{A,B}
2B
5C
9 B-D
Inf
Inf
{A.B.C}
2B
5C
9 B-D
6 C-E
Inf
{A.B.C.D}
2B
5C
9 B-D
6 C-E
10 C-E-F
{A.B.C.D.E}
2B
5C
9 B-D
6 C-E
10 C-E-F
{A.B.C.D.E.F}
2B
5C
9 B-D
6 C-E
10 C-E-F
c) Fast, loop free convergence
Fall, 2001
CS 640
2
Switching Hardware
• Design Goals
– throughput (depends on traffic model)
– scalability (a function of n)
Input
port
Output
port
Input
port
Output
port
Fabric
• Ports
Input
port
Output
port
Input
port
Output
port
– circuit management (e.g., map VCIs, route datagrams)
– buffering (input and/or output)
• Fabric
– as simple as possible
– sometimes do buffering (internal)
– Dealing with contention is an issue
Fall, 2001
CS 640
3
Crossbar Switches
• Basic idea – connect every
input n to every output
– Simple design
– Not generally scalable
• complexity grows at n2 rate
– Output port contention is an
issue
• Head-of-the-line blocking
when multiple input ports are
sending to one output port
Fall, 2001
CS 640
4
Knockout Switch
• Knockout switch is a design for an output port which deals
with contention on n outputs
– Reduces complexity – almost a crossbar
– Accepts l packets simultaneously where l < n
– Design minimizes cost for typical traffic flows
• Three components
– Packet filters recognize packet destinations
• Achieved by matching HW which considers port number
– Concentrator selects up to l packets for a port
• Drops the other packets
• This is the hard part due to need for fairness
• Our focus
– Queue buffers up to l packets at a time
• Simple FIFO queue
Fall, 2001
CS 640
5
The Concentrator
• The task of the concentrator is to fairly choose l out of
n packets destined for a single output port.
– Consider n = 8, l = 4
– Pair up packet and flip a coin to choose who “wins” and
goes on to the next stage.
– Each stage pairs “loosers” and “winners” in feedback
format.
– 4 packets will be dropped at the last stage
– All “winners” emerge at the same time – using delay
elements
Fall, 2001
CS 640
6
Knockout Switch Concentrator
Inputs
D = delay elements to insure
all packets exit at same time
D
D
D
D
D
D
D
D
D
D
D
1
D
D
D
2
3
4
Outputs
Fall, 2001
CS 640
7
Output buffer of Knockout switch
• You could implement a FIFO that runs l times faster than
the output of the concentrator
– Since each cycle generates l packets
• A more efficient approach is to implement an array of l
buffers preceded by a shifter
– Shifter insures buffers are filled in round robin order
• Insures that buffers never differ by more than one packet in their level
of occupancy
– Packets are read out one at a time in round robin order
• Insures packet order is preserved
• There can be buffer overflow when number of packets
arriving in each cycle is more than one for a period of time
Fall, 2001
CS 640
8
Knockout Switch Output Buffer
Shifter
Three packets arrive
(a)
Buffers
Shifter
Three more packets arrive
and are shifted right by three
positions. First packet leaves
(b)
Buffers
Shifter
(c)
One packets arrives and is
Shifted right by two positions.
Second packet leaves
Fall, 2001
CS 640
Buffers
9
Internet Protocol
• Runs on all hosts in the Internet and enables packets to be
routed between systems
– Key protocol for building networks
– Kahn-Cerf
• Datagram delivery of packets
– Connectionless and based on routing protocols
• Well defined packet format
• Global addressing
– Means for identifying Internet hosts
• Fragmentation and reassembly
– Since packets can be of varying size
• Error reporting
Fall, 2001
CS 640
10
An IP Internet – Network of Networks
Network 1 (Ethernet)
H7
H1
H2
R3
H8
H3
Network 4
(point-to-point)
Network 2 (Ethernet)
R1
R2
H4
Network 3 (FDDI)
H5
Fall, 2001
H6
CS 640
11
Protocol Stack – IP is Common to All
H1
H8
TCP
R1
IP
IP
ETH
Fall, 2001
R2
ETH
R3
IP
FDDI
FDDI
IP
PPP
CS 640
PPP
TCP
IP
ETH
ETH
12
Service Model
• Connectionless (datagram-based)
• Best-effort delivery (unreliable service)
–
–
–
–
packets are lost
packets are delivered out of order
duplicate copies of a packet are delivered
packets can be delayed for a long time
• Datagram format
0
4
Version
8
HLen
16
TOS
31
Length
Ident
TTL
19
Flags
Protocol
Offset
Checksum
SourceAddr
DestinationAddr
Options (variable)
Pad
(variable)
Data
Fall, 2001
CS 640
13
IPv4 Header Format
0
4
Version
8
HLen
16
TOS
31
Length
Ident
TTL
19
Flags
Protocol
Offset
Checksum
SourceAddr
DestinationAddr
Options (variable)
Pad
(variable)
Data
Fall, 2001
CS 640
14
Fragmentation and Reassembly
• Each network has some Maximum Transmission Unit (MTU)
– Largest datagram that a network can carry in a frame
• Strategy
– fragment when necessary (MTU < Datagram)
– try to avoid fragmentation at source host
• Due to overhead of reassembly
– re-fragmentation is possible
– fragments are self-contained datagrams
– delay reassembly until destination host
• Keep this functionality out of the network
– do not recover from lost fragments
• End hosts try to reassemble fragmented packets –if a fragment is lost…
• End hosts are encouraged to do MTU discovery
Fall, 2001
CS 640
15
Example
Fall, 2001
CS 640
16
Start of header
Ident = x
1
Offset = 0
Rest of header
Start of header
512 data bytes
Ident = x
0
Offset= 0
Start of header
Rest of header
Ident = x
1 Offset = 512
Rest of header
1400 data bytes
512 data bytes
Start of header
Ident = x
0 Offset = 1024
Rest of header
376 data bytes
Fall, 2001
CS 640
17
IPv4 Global Addresses
• Properties
– globally unique
– hierarchical: network + host
• Dot Notation
– 10.3.2.4
– 128.96.33.81
– 192.12.69.77
• AS’s refer to a network
type (assigned address
range)
Fall, 2001
A:
B:
C:
0
7
24
Network
Host
1 0
1 1 0
CS 640
14
16
Network
Host
21
8
Network
Host
18
Datagram Forwarding
• Every datagram contains destination’s address
• The “network part” of an IP address uniquely
identifies a single physical network (AS)
• If directly connected to destination network, then
forward to host
• If not directly connected to destination network, then
forward to some router
• Forwarding table maps network number into next
hop
– Mapping is based on routing algorithm
• Each host has a default router
• Each router maintains a forwarding table
Fall, 2001
CS 640
19
Internet Control Message Protocol
(ICMP)
•
•
•
•
•
•
•
Echo (ping)
Redirect (from router to source host)
Destination unreachable (protocol, port, or host)
TTL exceeded (so datagrams don’t cycle forever)
Checksum failed
Reassembly failed
Cannot fragment
Fall, 2001
CS 640
20
ICMP
• Uses IP but is a separate protocol in the network
layer
ICMP HEADER
IP HEADER
IP HEADER
PROTOCOL = 1
TYPE CODE CHECKSUM
IP DATA
Fall, 2001
REMAINDER OF ICMP
MESSAGE (FORMAT IS TYPE
SPECIFIC)
CS 640
21
Echo and Echo Reply
TYPE CODE CHECKSUM
IDENTIFIER SEQUENCE #
DATA ….
TYPE: 8 = ECHO, 0 = ECHO REPLY CODE; CODE = 0
IDENTIFIER
An identifier to aid in matching echoes and replies
SEQUENCE #
Same use as for IDENTIFIER
UNIX “ping” uses echo/echo reply
Fall, 2001
CS 640
22
Ping Example
C:\WINDOWS\Desktop>ping www.soi.wide.ad.jp
Pinging asari.soi.wide.ad.jp [203.178.137.88] with 32 bytes of data:
Reply from 203.178.137.88: bytes=32 time=253ms TTL=240
Reply from 203.178.137.88: bytes=32 time=231ms TTL=240
Reply from 203.178.137.88: bytes=32 time=225ms TTL=240
Reply from 203.178.137.88: bytes=32 time=214ms TTL=240
Ping statistics for 203.178.137.88:
Packets: Sent = 4, Received = 4, Lost = 0 (0% loss),
Approximate round trip times in milli-seconds:
Minimum = 214ms, Maximum = 253ms, Average = 230ms
Fall, 2001
CS 640
23
Redirect when no route to Destination
TYPE CODE CHECKSUM
NEW ROUTER ADDRESS
IP HEADER + 64 bits data
from original DG
TYPE = 5
CODE =
0 = Network redirect
1 = Host redirect
2 = Network redirect for specific TOS
3 = Host redirect for specific TOS
Fall, 2001
CS 640
24
Destination Unreachable
TYPE CODE CHECKSUM
UNUSED
IP HEADER + 64 bits data from original DG
TYPE = 3
CODE 0 = Net unreachable
1 = Host unreachable
2= Protocol unreachable
3 = Port unreachable
4 = Fragmentation needed but DF set
5 = Source route failed
Fall, 2001
CS 640
25
Time Exceeded
TYPE CODE CHECKSUM
UNUSED
IP HEADER + 64 bits data from original DG
TYPE = 11
CODE
0 = Time to live exceeded in transit
1 = Fragment reassembly time exceeded
Fall, 2001
CS 640
26
Source Quench
TYPE CODE CHECKSUM
UNUSED
IP HEADER + 64 bits data from original DG
TYPE = 4; CODE = 0
Indicates that a router has dropped the original DG or may
indicate that a router is approaching its capacity limit.
Correct behavior for source host is not defined.
Fall, 2001
CS 640
27
Traceroute
• UNIX utility - displays router used to get to a specified
Internet Host
• Operation
– router sends ICMP Time Exceeded message to source if TTL is
decremented to 0
– if TTL starts at 5, source host will receive Time Exceeded message
from router that is 5 hopes away
• Traceroute sends a series of probes with different TTL
values… and records the source address of the ICMP Time
Exceeded message for each
• Probes are formatted to that the destination host will send
an ICMP Port Unreachable message
Fall, 2001
CS 640
28
TraceRoute Example
C:\windows\desktop> tracert www.soi.wide.ad.jp
Tracing route to asari.soi.wide.ad.jp [203.178.137.88]
over a maximum of 30 hops:
1
19 ms
27 ms
23 ms 208.166.201.1
2
17 ms
13 ms
14 ms 204.189.71.9
3
25 ms
29 ms
29 ms aar1-serial4-1-0-0.Minneapolismpn.cw.net [208.174.7.5]
4
24 ms
27 ms
24 ms acr1.Minneapolismpn.cw.net [208.174.2.61]
5
26 ms
22 ms
23 ms acr2-loopback.Chicagochd.cw.net [208.172.2.62]
6
29 ms
29 ms
27 ms cand-w-private-peering.Chicagochd.cw.net [208.172.1.222]
7
28 ms
24 ms
28 ms 0.so-5-2-0.XL2.CHI2.ALTER.NET [152.63.68.6]
8
26 ms
27 ms
28 ms 0.so-7-0-0.XR2.CHI2.ALTER.NET [152.63.67.134]
9
25 ms
24 ms
26 ms 292.at-2-0-0.TR2.CHI4.ALTER.NET [152.63.64.234]
10
73 ms
74 ms
73 ms 106.ATM7-0.TR2.LAX2.ALTER.NET [146.188.136.142]
11
74 ms
76 ms
76 ms 198.ATM7-0.XR2.LAX4.ALTER.NET [146.188.249.5]
12
73 ms
75 ms
77 ms 192.ATM5-0.GW9.LAX4.ALTER.NET [152.63.115.77]
13
80 ms
73 ms
76 ms kdd-gw.customer.ALTER.NET [157.130.226.14]
14
84 ms
84 ms
91 ms 202.239.170.236
15
97 ms
81 ms
86 ms cisco1-eth-2-0.LosAngeles.wide.ad.jp [209.137.144.98]
16
174 ms
174 ms
178 ms cisco5.otemachi.wide.ad.jp [203.178.136.238]
17
201 ms
196 ms
194 ms cisco2.otemachi.wide.ad.jp [203.178.137.34]
18
183 ms
182 ms
196 ms foundry2.otemachi.wide.ad.jp [203.178.140.216]
19
183 ms
185 ms
178 ms gsr1.fujisawa.wide.ad.jp [203.178.138.252]
20
213 ms
205 ms
201 ms asari.soi.wide.ad.jp [203.178.137.88]
Trace complete.
Fall, 2001
CS 640
29