Advanced Computer

Networks
Week 4
Link layer, LANs: roadmap
 introduction
 error detection, correction
 multiple access protocols
 LANs
• addressing, ARP
• Ethernet
• switches
• VLANs
 a day in the life of a web
 link virtualization: MPLS
request
 data center networking
 802.3 Ethernet standards: link & physical layers

 many different Ethernet standards

• common MAC protocol and frame format
• different speeds: 2 Mbps, ... 100 Mbps, 1Gbps, 10 Gbps, 40 Gbps, 80 Gbps
• different physical layer media: fiber, cable

MAC protocol
application
and frame format
transport
network 100BASE-TX 100BASE-T2 100BASE-FX
link 100BASE-T4 100BASE-SX 100BASE-BX
physical

copper (twister pair) physical layer fiber physical layer

Ethernet switch
 Switch is a link-layer device: takes an active role
• store, forward Ethernet (or other type of) frames
• examine incoming frame’s MAC address, selectively forward frame
to one-or-more outgoing links when frame is to be forwarded on
segment, uses CSMA/CD to access segment
 transparent: hosts unaware of presence of switches
 plug-and-play, self-learning
• switches do not need to be configured
Switch: multiple simultaneous transmissions
 hosts have dedicated, direct
connection to switch A
 switches buffer packets C’ B
 Ethernet protocol used on each 1 2
incoming link, so: 6
3
• no collisions; full duplex 5 4
• each link is its own collision
domain B’ C
A’
 switching: A-to-A’ and B-to-B’ can transmit
simultaneously, without collisions switch with six
interfaces (1,2,3,4,5,6)
Switch: multiple simultaneous transmissions
 hosts have dedicated, direct
connection to switch A
 switches buffer packets C’ B
 Ethernet protocol used on each 1 2
incoming link, so: 6
3
• no collisions; full duplex 5 4
• each link is its own collision
domain B’ C
A’
 switching: A-to-A’ and B-to-B’ can transmit
simultaneously, without collisions switch with six
interfaces (1,2,3,4,5,6)
• but A-to-A’ and C to A’ can not happen
simultaneously
Switch forwarding table
Q: how does switch know A’ reachable via
interface 4, B’ reachable via interface 5? A
C’ B
A: each switch has a switch table, each
entry: 1 2
6
 (MAC address of host, interface to reach 3
5 4
host, time stamp)
 looks like a routing table! B’ C
A’
Q: how are entries created, maintained
in switch table?
 something like a routing protocol?
Switch: self-learning
Source: A

 switch learns which hosts Dest: A’

A A’
can be reached through A
which interfaces C’ B
• when frame received, switch 1 2
“learns” location of sender: 6
3
incoming LAN segment 5 4

• records sender/location pair B’ C

A’
in switch table
Switch table
MAC addr interface TTL (initially empty)
A 1 60
Self-learning, forwarding: example Source: A
Dest: A’

 frame destination, A’, A A’

location unknown: flood A
C’ B
 destination A location
1
known: selectively send 6A A’
2

on just one link 5 4

3

B’ C
A’ A A’

MAC addr interface TTL

A 1 60 switch table
A’ 4 60 (initially empty)
Interconnecting switches
self-learning switches can be connected together:

S4

S1
S3
A S2
F
D I
B C
G H
E

Q: sending from A to G - how does S1 know to forward frame destined to

G via S4 and S3?
 A: self learning! (works exactly the same as in single-switch case!)
 Campus Network Campus network:
 4 firewalls
to off campus  10 routers
border border  2000+ network switches
 6000 wireless access
points
Core core
 30000 active wired
network jacks
 55000 active end-user
wireless devices
Agg1 Agg2 Agg3 Agg4 WiFi
... firewall data center … all built,
... ... ... ...
Wireless Wireless
operated,
building
closets
Controller Controller maintained by ~15
people
 Campus Network - Detail
Protocols Link Speeds

to off campus eBGP 10G;

100G pending
inter-domain
border border routing

iBGP
40G & 100G
IS-IS
Core core
intra-domain
routing

IS-IS 40G

Agg1 Agg2 Agg3 Agg4 WiFi

... firewall data center
... ... ... ...
Wireless Wireless layer-2 Ethernet
building Controller Controller 10G & 1G
closets switching
Switches vs. routers application
transport
both are store-and-forward: datagram network
frame link
 routers: network-layer devices (examine physical link frame
network-layer headers) physical

 switches: link-layer devices (examine switch

link-layer headers) network datagram
link
both have forwarding tables: physical
frame

 routers: compute tables using routing application

algorithms, IP addresses transport
 switches: learn forwarding table using network
flooding, learning, MAC addresses link
physical

6-13
Link layer, LANs: roadmap
 introduction
 error detection, correction
 multiple access protocols
 LANs
• addressing, ARP
• Ethernet
• switches
• VLANs
 a day in the life of a web
 link virtualization: MPLS
request
 data center networking
Virtual LANs (VLANs): motivation
Q: what happens as LAN sizes scale, users change point of attachment?
single broadcast domain:
 scaling: all layer-2 broadcast traffic
(ARP, DHCP, unknown MAC) must
cross entire LAN
Computer  efficiency, security, privacy issues
Science EE
Virtual LANs (VLANs): motivation
Q: what happens as LAN sizes scale, users change point of attachment?
single broadcast domain:
 scaling: all layer-2 broadcast traffic
(ARP, DHCP, unknown MAC) must
cross entire LAN
Computer  efficiency, security, privacy, efficiency
Science EE issues
administrative issues:
 CS user moves office to EE - physically
attached to EE switch, but wants to
remain logically attached to CS
switch
Link Layer: 6-16
Port-based VLANs port-based VLAN: switch ports grouped (by
switch management software) so that
single physical switch ……
Virtual Local Area
Network (VLAN) 7 9 15
1

switch(es) supporting
2 8 10 16

… …
VLAN capabilities can
be configured to define EE (VLAN ports 1-8) CS (VLAN ports 9-15)

multiple virtual LANS … operates as multiple virtual switches

over single physical LAN
infrastructure.
1 7 9 15

2 8 10 16

… …
EE (VLAN ports 1-8) CS (VLAN ports 9-15)
Port-based VLANs
 traffic isolation: frames to/from ports
1-8 can only reach ports 1-8
• can also define VLAN based on MAC
addresses of endpoints, rather than
switch port
 dynamic membership: ports can be
dynamically assigned among VLANs 1 7 9 15

2 8 10 16

 forwarding between VLANS: done via … …

routing (just as with separate switches) EE (VLAN ports 1-8) CS (VLAN ports 9-15)

• in practice vendors sell combined switches

plus routers
VLANS spanning multiple switches

1 7 9 15 1 3 5 7
2 8 10 16 2 4 6 8

… … …
EE (VLAN ports 1-8) CS (VLAN ports 9-15) Ports 2,3,5 belong to EE VLAN
Ports 4,6,7,8 belong to CS VLAN

trunk port: carries frames between VLANS defined over multiple

physical switches
 frames forwarded within VLAN between switches can’t be vanilla 802.1
frames (must carry VLAN ID info)
 802.1q protocol adds/removed additional header fields for frames
forwarded between trunk ports
802.1Q VLAN frame format
type
dest. source data (payload) CRC
preamble address address 802.1 Ethernet frame

type
dest. source CRC
preamble address address data (payload) 802.1Q frame

2-byte Tag Protocol Identifier Recomputed

(value: 81-00) CRC
Tag Control Information
(12 bit VLAN ID field, 3 bit priority field like IP TOS)
EVPN: Ethernet VPNs (aka VXLANs)

5
1 7 9 15 1 3 7
2 8 10 16 IP Ethernet 2 4 6 8
datagram frame
… … …
Sunnyvale Bangalore
data center Ethernet data center

Layer-2 Ethernet switches logically connected to each other (e.g., using IP as an

underlay)
 Ethernet frames carried within IP datagrams between sites
 “tunneling scheme to overlay Layer 2 networks on top of Layer 3 networks ... runs over
the existing networking infrastructure and provides a means to "stretch" a Layer 2
network.” [RFC 7348]
Link layer, LANs: roadmap
 introduction
 error detection, correction
 multiple access protocols
 LANs
• addressing, ARP
• Ethernet
• switches
• VLANs
 a day in the life of a web
 link virtualization: MPLS request
 data center networking
Multiprotocol label switching (MPLS)
 goal: high-speed IP forwarding among network of MPLS-capable
routers, using fixed length label (instead of shortest prefix matching)
• faster lookup using fixed length identifier
• borrowing ideas from Virtual Circuit (VC) approach
• but IP datagram still keeps IP address!

Ethernet remainder of Ethernet

remainder frame, including
of Ethernet IP
frame, including IP
MPLS header
header header header
with IP source, destination
with IP source, addresses
destination addresses

label Exp S TTL

20 3 1 5
MPLS capable routers
 a.k.a. label-switched router
 forward packets to outgoing interface based only on label
value (don’t inspect IP address)
• MPLS forwarding table distinct from IP forwarding tables
 flexibility: MPLS forwarding decisions can differ from
those of IP
• use destination and source addresses to route flows to same
destination differently (traffic engineering)
• re-route flows quickly if link fails: pre-computed backup paths
MPLS versus IP paths

R6
D
IP router
R4 R3
R5
A
R2

 IP routing: path to destination determined by destination address alone

MPLS versus IP paths
IP/MPLS entry router (R4) can use different MPLS routes to
A based, e.g., on IP source address or other fields
R6
D
IP router
R4 R3
R5
IP/MPLS router
A
R2 R1

 IP routing: path to destination determined by destination address alone

 MPLS routing: path to destination can be based on source and
destination address
• flavor of generalized forwarding (MPLS 10 years earlier)
• fast reroute: precompute backup routes in case of link failure
MPLS signaling
 modify OSPF, IS-IS link-state flooding protocols to carry info
used by MPLS routing:
• e.g., link bandwidth, amount of “reserved” link bandwidth
 entry MPLS router uses RSVP-TE signaling protocol to set up
MPLS forwarding at downstream routers

RSVP-TE
R6
D
R4 R3
R5 modified
link state
flooding A
R2 R1
MPLS forwarding tables
in out out
label label dest interface
10 A 0 in out out
12 D 0 label label dest interface

8 A 1 10 6 A 1
12 9 D 0

R6
0 0
D
1 1
R4 R3
R5
0 0
A
R2 R1
in out out in out out
label label dest interface label label dest interface
8 6 A 0 6 - A 0
Link layer, LANs: roadmap
 introduction
 error detection, correction
 multiple access protocols
 LANs
• addressing, ARP
• Ethernet
• switches
• VLANs
 a day in the life of a web
 link virtualization: MPLS
request
 data center networking
Datacenter networks
10’s to 100’s of thousands of hosts, often closely coupled, in
close proximity:
 e-business (e.g. Amazon)
 content-servers (e.g., YouTube, Akamai, Apple, Microsoft)
 search engines, data mining (e.g., Google)

challenges:
 multiple applications, each serving
massive numbers of clients
 reliability
 managing/balancing load, avoiding
processing, networking, data
bottlenecks Inside a 40-ft Microsoft container, Chicago data center
Datacenter networks: network elements
Border routers
 connections outside datacenter

Tier-1 switches
 connecting to ~16 T-2s below

Tier-2 switches
 connecting to ~16 TORs below
… … … …
Top of Rack (TOR) switch
… … … …  one per rack
 100G-400G Ethernet to blades
Server racks
 20- 40 server blades: hosts
Datacenter networks: network elements
Facebook F16 data center network topology:

[Link] (posted 3/2019)

Datacenter networks: multipath
 rich interconnection among switches, racks:
• increased throughput between racks (multiple routing paths possible)
• increased reliability via redundancy

9 10 11 12 13 14 15 16

two disjoint paths highlighted between racks 1 and 11

Datacenter networks: application-layer routing
Internet
load balancer:
application-layer
routing
 receives external
Load client requests
balancer
 directs workload
within data center
… … … …  returns results to
external client
… … … …
(hiding data center
internals from client)
 Datacenter networks: protocol innovations
 link layer:
• RoCE: remote DMA (RDMA) over Converged Ethernet
 transport layer:
• ECN (explicit congestion notification) used in transport-layer congestion
control (DCTCP, DCQCN)
• experimentation with hop-by-hop (backpressure) congestion control
 routing, management:
• SDN widely used within/among organizations’ datacenters
• place related services, data as close as possible (e.g., in same rack or nearby
rack) to minimize tier-2, tier-1 communication

Google Networking: Infrastructure and Selected Challenges (Slides:

[Link]
ORION: Google’s new SDN control plane for internal
datacenter (Jupiter) + wide area (B4) network
 routing (intradomain, iBGP), traffic Orion SDN architecture and core apps
engineering: implemented in applications
on top of ORION core
 edge-edge flow-based controls (e.g.,
CoFlow scheduling) to meet contract SLAs
 management: pub-sub distributed
microservices in Orion core, OpenFlow for
switch signaling/monitoring

Note:
 no routing protocols, congestion control (partially) also managed by SDN rather
than by protocol
 are protocols dying?
 Network Layer:
Logical Addressing
19-1 IPv4 ADDRESSES

An IPv4 address is a 32-bit address that uniquely and

universally defines the connection of a device (for
example, a computer or a router) to the Internet.

Topics discussed in this section:

Address Space
Notations
Classful Addressing
Classless Addressing
Network Address Translation (NAT)
Figure 19.1 Dotted-decimal notation and binary notation for an IPv4 address
 Example 19.1

Change the following IPv4 addresses from binary

notation to dotted-decimal notation.

Solution
We replace each group of 8 bits with its equivalent
decimal number (see Appendix B) and add dots for
separation.
 Example 19.2

Change the following IPv4 addresses from dotted-decimal

notation to binary notation.

Solution
We replace each decimal number with its binary
equivalent (see Appendix B).
 Example 19.3

Find the error, if any, in the following IPv4 addresses.

Solution
a. There must be no leading zero (045).
b. There can be no more than four numbers.
c. Each number needs to be less than or equal to 255.
d. A mixture of binary notation and dotted-decimal
notation is not allowed.
Note

In classful addressing, the address

space is divided into five classes:
A, B, C, D, and E.
Figure 19.2 Finding the classes in binary and dotted-decimal notation
 Example 19.4

Find the class of each address.

a. 00000001 00001011 00001011 11101111
b. 11000001 10000011 00011011 11111111
c. [Link]
d. [Link]

Solution
a. The first bit is 0. This is a class A address.
b. The first 2 bits are 1; the third bit is 0. This is a class C
address.
c. The first byte is 14; the class is A.
d. The first byte is 252; the class is E.
Table 19.1 Number of blocks and block size in classful IPv4 addressing
Note

In classful addressing, a large part of the

available addresses were wasted.
Table 19.2 Default masks for classful addressing
Note

Classful addressing, which is almost

obsolete, is replaced with classless
addressing.