Transcript 3rd Edition: Chapter 3

Chapter 4
Network Layer
Computer
Networking: A Top
Down Approach

CPSC 335 Data Communication Systems
Readings: 4.6.3, 4.7, 4.7.1, 4.7.2

David Nguyen

6th edition
Jim Kurose, Keith Ross
Addison-Wesley
March 2012
Adapted from Kurose Ross
David Kauchak (Stanford University)
Transport Layer 3-1
Chapter 4: outline
4.1 introduction
4.2 virtual circuit and
datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol




datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
 link state
 distance vector
 hierarchical routing
4.6 routing in the Internet
 RIP
 OSPF
 BGP
4.7 broadcast and multicast
routing
Network Layer 4-2
Internet inter-AS routing: BGP

BGP (Border Gateway Protocol): the de
facto inter-domain routing protocol
 “glue that holds the Internet together”

BGP provides each AS a means to:
 eBGP: obtain subnet reachability information
from neighboring ASs.
 iBGP: propagate reachability information to all
AS-internal routers.
 determine “good” routes to other networks
based on reachability information and policy.

allows subnet to advertise its existence to
rest of Internet: “I am here”
Network Layer 4-3
BGP basics

BGP session: two BGP routers (“peers”) exchange BGP
messages:
 advertising paths to different destination network prefixes
 exchanged over semi-permanent TCP connections

when AS3 advertises a prefix to AS1:
 AS3 promises it will forward datagrams towards that prefix
3c
3b
other
networks
3a
BGP
message
AS3
2c
1c
1a
AS1
1d
2a
1b
2b
other
networks
AS2
Network Layer 4-4
Chapter 4: outline
4.1 introduction
4.2 virtual circuit and
datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol




datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
 link state
 distance vector
 hierarchical routing
4.6 routing in the Internet
 RIP
 OSPF
 BGP
4.7 broadcast and multicast
routing
Network Layer 4-5
Broadcast routing
deliver packets from source to all other nodes
 source duplication is inefficient:

duplicate
duplicate
creation/transmission
R1
R1
duplicate
R2
R2
R3
R4
source
duplication
R3
R4
in-network
duplication
Network Layer 4-6
In-network duplication

flooding: when node receives broadcast
packet, sends copy to all neighbors
 problems: cycles & broadcast storm

controlled flooding: node only broadcasts pkt
if it hasn’t broadcast same packet before
 node keeps track of packet ids already
broadcasted

spanning tree:
 no redundant packets received by any node
Network Layer 4-7
Spanning tree
= subset of edges with no cycle that
connects all vertices
 nodes then forward/make copies only along
spanning tree

A
A
B
B
c
c
D
F
D
E
F
G
(a) broadcast initiated at A
E
G
(b) broadcast initiated at D
Network Layer 4-8
Minimum spanning tree
= subset of edges with no cycle and the
lowest weight that connects all vertices
 ~ plow snow on roads so that cities stay
connected during calamities

Input: An undirected, G=(V,E)
 Output: A tree T=(V,E’) where E’  E that
minimizes

weight(T )   we
eE '
MST example
1
A
4
B
3
C
4
4
E
2
D
4
6
5
F
A
1
C
2
4
B
E
D
4
5
F
MSTs

Can a MST have a cycle?
A
1
C
2
4
B
E
4
D
4
5
F
MSTs

Can an MST have a cycle?
A
1
C
2
4
B
E
D
4
5
F
Applications?

Connectivity
 Networks (e.g. communications)
 Circuit desing/wiring
hub/spoke models (e.g. flights,
transportation)
 Traveling salesman problem?

Prim-Jarnik algorithm to find
MST

Developed in 1930 by Czech Jarnik and later
independently by American Prim in 1957
Prim-Jarnik algorithm
Prim-Jarnik algorithm
Prim-Jarnik algorithm

Start at some root node and build out the MST by adding
the lowest weighted edge at the frontier
Prim-Jarnik
1
A
4
B
3
C
4
4
E
2
D
4
6
MST
5
F
A
C
E
B
D
F
Prim-Jarnik
1
A
4
B
3
C
4
4
E
2
D
4
6
5
F

MST


A
C
E
B
D
F


0
Prim-Jarnik
1
A
4
B
3
C
4
4
E
2
D
4
6
5
F

MST
4
5
A
C
E
B
D
F

6
0
Prim-Jarnik
1
A
4
B
3
C
4
4
E
2
D
4
6
5
F

MST
4
5
A
C
E
B
D
F

6
0
Prim-Jarnik
1
A
4
B
3
C
4
4
E
2
D
4
6
5
F
1
MST
4
5
A
C
E
B
D
F
4
2
0
Prim-Jarnik
1
A
4
B
3
C
4
4
E
2
D
4
6
5
F
1
MST
4
5
A
C
E
B
D
F
4
2
0
Prim-Jarnik
1
A
4
B
3
C
4
4
E
2
D
4
6
5
F
1
MST
4
5
A
C
E
B
D
F
4
2
0
Prim-Jarnik
1
A
4
B
3
C
4
4
E
2
D
4
6
5
F
1
MST
4
5
A
C
E
B
D
F
4
2
0
Prim-Jarnik
1
A
4
B
3
C
4
4
E
2
D
4
6
5
F
1
MST
4
5
A
C
E
B
D
F
4
2
0
Prim-Jarnik
1
A
4
B
3
C
4
4
E
2
D
4
6
5
F
1
MST
4
5
A
C
E
B
D
F
4
2
0
Prim-Jarnik
1
A
4
B
3
C
4
4
E
2
D
4
6
5
F
1
MST
4
5
A
C
E
B
D
F
4
2
0
Prim-Jarnik
1
A
4
B
3
C
4
4
E
2
D
4
6
5
F
1
MST
4
5
A
C
E
B
D
F
4
2
0
Multicast routing: problem statement



deliver packets from source to some other nodes
tree: not all paths between routers used
shared-tree: same tree used by all group members

source-based: different tree from each sender to rcvrs
legend
group
member
not group
member
router
with a
group
member
router
without
group
member
shared tree
source-based trees
Network Layer 4-30
Chapter 4: done!
4.1 introduction
4.2 virtual circuit and
datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
 datagram format, IPv4
addressing, ICMP, IPv6
4.5 routing algorithms
 link state, distance vector,
hierarchical routing
4.6 routing in the Internet
 RIP, OSPF, BGP
4.7 broadcast and multicast
routing
understand principles behind network layer services:
 network layer service models, forwarding versus routing
how a router works, routing (path selection), broadcast,
multicast
 instantiation, implementation in the Internet

Network Layer 4-31
How to get a dream job at big IT companies?
Tips based on personal experience and “Cracking the Coding Interview”
GOOGLE AND AMAZON
INTERVIEW TIPS!
Transport Layer 3-32
What questions should you
ask the interviewer?
Quality of your questions will be a factor,
whether subconsciously or consciously, in
their decisions
 You can - and should - prepare questions in
advance
 Doing research on the company or team
may help you with preparing questions.

Transport Layer 3-33
Genuine Questions
These are the questions you actually want
to know
 “How much of your day do you spend
coding?”
 “How many meetings do you have every
week?”
 “What is the ratio of testers to developers
to product managers? What is the
interaction like? How does project planning
happen on the team?”

Transport Layer 3-34
Insightful Questions
to demonstrate your deep knowledge of
programming or technologies
 “I noticed that you use technology X.How
do you handle problem Y?”
 “Why did the product choose to use the X
protocol over the Y protocol? I know it has
benefits like A, B, C, but many companies
choose not to use it because of issue D.”

Transport Layer 3-35
Passion Questions
to demonstrate your passion for
technology
 “I’m very interested in scalability. Did you
come in with a background in this, or what
opportunities are there to learn about it?”
 “I’m not familiar with technology X, but it
sounds like a very interesting solution.
Could you tell me a bit more about how it
works?”

Transport Layer 3-36