Transcript Review

Final Exam
Coverage and distribution of marks
FTP Server Assignment
10
Application Layer
10
Transport
10
Network
10
Link-Layer
10
Security
10
Total
60
Note
• Wireless Networking is not going to be
included in the Final Exam.
Types of Questions
• Define terms, identify technologies,
explain purpose
• Explain concepts and protocols
– Using diagrams (label them properly)
– Appropriate variables (or parameters)
• Solve problems (e.g. apply DV Algorithm,
CRC)
MAC Protocols: a taxonomy
Three broad classes:
• Channel Partitioning Protocols
– divide channel into smaller pieces (time slots, frequency
bands, multiple access codes)
– allocate piece to node for exclusive use
• Random Access Protocols
– allow collisions
– recover from collisions
• Taking turns Protocols
– tightly coordinate shared access to avoid collisions
Animation
Channel Partitioning (CDMA)
CDMA (Code Division Multiple Access)
• Sender: sends encoded data bits simultaneously
• Receiver: assigned a unique code (i.e. code set partitioning)
• Has been used by military; now used mostly in wireless
broadcast channels (cellular, satellite,etc)
• all users share same frequency, but each user has own
''chipping'' sequence (i.e., code) to encode data
• encoded signal = (original data) X (chipping sequence)
• decoding: inner-product of encoded signal and chipping
sequence
• Advantage: allows multiple users to coexist and transmit
simultaneously with minimal interference (if codes are
orthogonal)
CDMA Encode/Decode
M mini slots
are assigned
to each data
bit
CDMA: two-sender interference
Assumption: interfering
bit signals are additive
Random Access protocols
• When node has packet to send
– transmit at full rate (R) of channel
– no a priori coordination among nodes
• two or more transmitting nodes -> collision!!,
• random access MAC protocol specifies:
– how to detect collisions
– how to recover from collisions (e.g., via delayed
retransmissions)
• Examples of random access MAC protocols:
– slotted ALOHA
– ALOHA
– CSMA and CSMA/CD
CSMA:
(Carrier Sense Multiple Access)
CSMA: listen before transmit:
• If channel sensed idle: transmit entire pkt
• If channel sensed busy, defer transmission
– Persistent CSMA: retry immediately with
probability p when channel becomes idle (may
cause instability)
– Non-persistent CSMA: retry after random time
interval
• human analogy: don't interrupt
others!
RULES:
Animation
•Listen before speaking (carrier sensing)
• If someone else begins talking at the same
time, stop talking (collision detection)
Channel propagation
delay
CSMA collisions
4 nodes attached to a linear broadcast
bus; Horizontal axis shows position of
each node in space
collisions can occur:
propagation delay means
two nodes may not yet
hear each other's
transmission
collision:
entire packet transmission
time wasted
note:
D senses the
channel is idle at t1
role of distance and
propagation delay in
determining collision prob.
spatial layout of nodes along ethernet
CSMA/CD (Collision Detection)
CSMA/CD: carrier sensing, deferral as in CSMA
– collisions detected within short time
– colliding transmissions aborted, reducing channel
wastage
– persistent or non-persistent retransmission
• collision detection:
– easy in wired LANs: measure signal strengths,
compare transmitted, received signals
– difficult in wireless LANs: receiver shut off while
transmitting
• human analogy: the polite conversation
CSMA/CD collision detection
4 nodes attached to
a linear broadcast
bus
From Network to Link-Layer
Datagram to Frame
Recall earlier routing discussion
Starting at A, given IP
datagram addressed to B:
A
223.1.1.1
223.1.2.1
 look up net. address of B, find B
on same net. as A
 link layer send datagram to B
inside link-layer frame
frame source,
dest address
B’s MAC A’s MAC
addr
addr
223.1.1.2
223.1.1.4 223.1.2.9
B
223.1.1.3
datagram source,
dest address
A’s IP
addr
B’s IP
addr
223.1.3.27
223.1.3.1
IP payload
datagram
frame
Additional addresses!
223.1.2.2
223.1.3.2
E
ARP: Address Resolution Protocol
ARP for Ethernet (RFC 826), Intro to ARP,TCP/IP Tutorial (RFC 1180)
Question: how to determine
MAC address of B
given B's IP address?
• Each IP node (Host,
Router) on LAN has
ARP module, table
Resides in RAM
• ARP Table: IP/MAC
address mappings for
some LAN nodes
< IP address; MAC address;
TTL>
<………….. >
– TTL (Time To Live): time after
which address mapping will
be forgotten (typically 20 min)
ARP: Address Resolution Protocol
How is ARP Table initialized?
• It’s plug-and-play!
• Not configured by Network Administrator
• Tables are automatically updated when one node is disconnected
from subnet
ARP protocol: A Scenario
• A knows B's IP address, wants to learn physical address of B
• A broadcasts ARP query pkt, containing B's IP address
– all machines on LAN receive ARP query
Passes ARP packet within the
frame up to its parent node
• B receives ARP packet, replies to A with its (B's) physical layer
address
Only one node (node with IP address=DEST
IP in the ARP packet) sends back to the
querying node a response ARP packet with
the desired mapping
• A caches (saves) IP-to-physical address pairs until information
becomes old (times out)
– soft state: information that times out (goes away) unless
refreshed
In turn, the querying node can then update
its ARP Table and send its IP datagram
Routing to another LAN
Two Types of Nodes:
• Hosts
• Routers
2 interfaces, 2 IP addresses, 2
ARP modules, 2 adapters (2
MAC addresses)
Router
• has an IP address for each of its interfaces
• has an ARP module for each of its interfaces
• has an adapter for each of its interfaces
• each adapter has its own MAC Address
A
R
Network 1: Network address:
111.111.111/24
B
Network 2:
Network address:
222.222.222/24
Routing to another LAN
routing from A to B via R
In routing table at source Host, find router 111.111.111.110
• In ARP table at source, find MAC address E6-E9-00-17BB-4B, etc
A
R
Network 1: Network address:
111.111.111/24
B
Network 2:
Network address:
222.222.222/24
How a HOST on Subnet 1 sends a datagram to a HOST on Subnet 2?
• A creates IP packet with source A, destination B
Passes datagram to adapter
Host A must indicate to its
adapter an appropriate MAC
address (DEST)
Note: Before sending the frame, MAC address must be acquired (should
match one of the nodes in subnet; otherwise, will be lost). Then, frame is
sent to Subnet.
A
R
B
• A uses ARP to get R's physical layer address for
111.111.111.110 (adapter side)
Note: Router interface
• handles routing; uses Forwarding Table
Adapter
• uses ARP to find MAC address
A
R
B
• (adapter) A creates Ethernet frame with R's physical address as
dest, Ethernet frame contains A-to-B IP datagram
• (adapter) A's data link layer sends Ethernet frame
• (adapter) R's data link layer receives Ethernet frame
– Passes frame to Network Layer
• (network layer) R removes IP datagram from Ethernet frame,
sees its destined to B
– Using router R’s Forwarding table) – table tells R to forward
datagram via router interface 222.222.222.220
• R’s interface passes datagram to its adaptor
A
R
B
• (adapter) R uses ARP to get B's physical layer
address
• (adapter) R creates frame containing A-to-B IP
datagram sends to B
A
R
B
CRC
Pseudo code, Manual Calculation of CRC
See sample computations
sample
Ethernet: uses CSMA/CD
Run without explicit coordination with other adapters on the Ethernet
A: sense channel, if idle
then {
transmit and monitor the channel;
If another transmission is detected
then {
Connectionless
unreliable service to
Network Layer
No signal energy in
channel for 96 bit
times
abort and send jam signal;
update # collisions;
delay as required by exponential backoff algorithm;
goto A
}
else {done with the frame; set collisions to zero}
}
else {wait until ongoing transmission is over and goto A}
Ethernet’s CSMA/CD (more)
Jam Signal: make sure all other transmitters are
aware of collision; 48 bits;
Exponential Backoff:
• Goal: adapt retransmission attempts to estimated
=min(10, num of collisions)
current load
– heavy load: random wait will be longer
• first collision: choose K randomly from {0, 2m-1};
delay is K x 512 bit transmission times
• after second collision: choose K from {0,1,2,3}…
• after ten or more collisions, choose K from
{0,1,2,3,4,…,1023}
For 10Mbps Ethernet, time to transmit 1 bit = 0.1 microseconds
Network Devices
Repeaters, Hubs, Bridges, Routers, Switches
Definition of Terms
Hubs
• Physical Layer devices: essentially repeaters
operating at bit levels: repeat received bits on
one interface to all other interfaces
• Hubs can be arranged in a hierarchy (or
multi-tier design), with backbone hub at its top
Backbone Bridge
Bridges Spanning Tree
• for increased reliability, it is desirable to have
redundant, alternate paths from source to
dest
• with multiple simultaneous paths, cycles
result - bridges may multiply and forward
frame forever
Disabled
• solution: organize bridges in a spanning tree
by disabling subset of interfaces
Bridge Learning: example
Suppose C sends a frame to D and D replies back with
a frame to C

C sends the frame to the bridge, but the bridge has no info. about D, so it floods both
LANs



bridge notes that C is on port 1
frame ignored on upper LAN
frame received by D
Bridge Learning: example

D generates a reply to C, sends

bridge sees frame from D

bridge notes that D is on interface 2

bridge knows C on interface 1, so it selectively forwards the frame out via
interface 1
Routers vs. Bridges
Routers + and + arbitrary topologies can be supported, cycling is limited
by TTL counters (and good routing protocols)
+ provide firewall protection against broadcast storms
- require IP address configuration (not plug and play)
- require higher processing bandwidth
• bridges do well in small (few hundred hosts) while
routers used in large networks (thousands of hosts)
Ethernet Switches (more)
Institutional Network using a combination of hubs, Ethernet switches,
router
Dedicated
Shared
Interconnection Devices
COMPARISON OF FEATURES
HUBS
BRIDGES
ROUTERS
ETHERNET
SWITCHES
Traffic
Isolation
No
Yes
Yes
Yes
Plug-andPlay
Yes
Yes
No
Yes
No
No
Yes
No
Yes
No
No
Yes
Optimal
Routing
Cutthrough
Let’s see some captured runs of
the DV algorithm
Review Pseudo codes as well
Node Update
Node 0
0
1
2
0
999
1
999
1
2
999
999
3
999
999 999
3
Min
999 999 999
999 999
3
0
1
999
3
7
7
3 + 70 = 73
Rcv event, t=1.484 at 0; Source: 2,
Dest: 0
Min
0
3
1
70
2
0
3
2
srtpkt2
0
1
2
3
Min
0
999
999
999
999
0
1
999
1
73
999
1
2
999
999
3
999
3
3
999
999
5
7
5
Node Update
Node 0
Apply Poisoned Reverse
73 turns 999
0
1
2
3
Min
0
999
999
999
999
0
1
999
1
999
999
1
2
999
999
3
999
3
3
999
999
5
7
5
srtpkt0
Min
0
0
1
1
2
3
3
5
Send new mincost to neighbors via tolayer2()
DV Algorithm
There are four routers connected via certain links (figure). Suppose that the following table
is used for the initialisation of C’s routing table:
C
dest
via
A
B
D
A
1
∞
∞
B
∞
3
∞
D
∞
∞
2
And the minimum cost is an array of 4 integers in the order A, B, C, D:
A advertises its minimum costs as: 0, 4, 1, ∞
B advertises its minimum costs as: 4, 0, 3, 1
D advertises its minimum costs as: ∞, 1, 2, 0
Show the first update on C’s table if C simultaneously receives packets with
the minimum cost information from the routers A, B and D
The End.
Good luck!