Network Layer: The Most Complex Layer

Download as ppt, pdf, or txt
Download as ppt, pdf, or txt
You are on page 1of 75

Network Layer

Network

Requires the coordinated actions of multiple,


geographically distributed network elements
(switches & routers)
Must be able to deal with very large scales

Layer: the most complex layer

Billions of users (people & communicating devices)

Biggest Challenges

Addressing: where should information be directed to?


Routing: what path should be used to get information
there?

Packet Switching
t1

t0
Network

Transfer of information as payload in data packets


Packets undergo random delays & possible loss
Different applications impose differing requirements
on the transfer of information

Perspectives of Packet Networks


External

Services that the network provides to the transport layer


Services are independent of the underlying network
Whether the network service requires setting up of connections
Whether data transfer requires any quality-of-service guarantees

Internal

View of the network

Operation of the network

Considers physical topology of the network and its interconnection


Approaches used to direct information datagram, virtual circuit
Addressing and routing procedures
Deal with congestion inside the network
Traffic management inside the network

Network Service
Messages

Messages
Segments

Transport
layer

Transport
layer
Network
service

Network
service

End
system

Network
layer

Network
layer

Network
layer

Network
layer

Data link
layer

Data link
layer

Data link
layer

Data link
layer

Physical
layer

Physical
layer

Physical
layer

Physical
layer

End
system

Network layer can offer a variety of services to transport layer


Connection-oriented service or connectionless service
Best-effort or delay/loss guarantees

Connectionless vs. Connection-oriented


Connectionless :

Only two basic interactions between transport and network layer

User can request packet transmission at any time

Request to network layer to send a packet


Indication from network layer that a packet has arrived
No need to inform network layer ahead of time

Responsibility for error control, sequencing and flow control on transport-layer

Connection-oriented :

Connection-setup required

Allows usage and quality-of-service negotiations

Network layer must be informed about the new flow to be sent to the network
Network layer maintains state information about the flows it is handling
Network resources may be allocated

Connection-termination required
Complex than connectionless service

Network Service vs. Operation


Network Service
Connectionless (UDP)

Datagram Transfer

Connection-Oriented (TCP)

Internal Network Operation


Connectionless

Reliable and possibly


constant bit rate transfer

Datagram operation
IP

Connection-Oriented

Virtual Circuit operation


Telephone connection
ATM

Various combinations are possible


Connection-oriented service over Connectionless operation
Connectionless service over Connection-Oriented operation
Context & requirements determine what makes sense

Complexity at the Edge or in the Core?


C
12

12

End system

4 3 21

21
2
1
1

12

2
21

Medium

A
1

Physical layer entity

Data link layer entity

2
12

2
1

Network
3

Network layer entity

2
21

End system

123 4

Network layer entity

Transport layer entity

Need for the network to grow to very large scale

keep the core of the network simple (connectionless packet network)

provide necessary complexity at the edge

Network Layer Functions


Essential
Routing: mechanisms for determining the
set of best paths for routing packets requires
the collaboration of network elements
Forwarding: transfer of packets from NE
inputs to outputs
Priority & Scheduling: determining order of
packet transmission in each NE
Optional: congestion control, segmentation &
reassembly, security

Packet-Switching
Networks
Datagrams and Virtual Circuits

The Switching Function

Dynamic interconnection of inputs to outputs


Enables dynamic sharing of transmission resource
Two fundamental approaches:

Connectionless
Connection-Oriented: Call setup control, Connection control

Backbone Network
Switch

Access Network

Packet Switching Network


User
Transmission
line
Network
Packet
switch

Packet switching network


Transfers packets
between users
Transmission lines +
packet switches
(routers)
Origin in message
switching
Two modes of operation:
Connectionless
Virtual Circuit

Message Switching

Message

Message
Message

Source
Message

Switches

Destination

Message switching
invented for telegraphy
Entire messages
multiplexed onto shared
lines, stored & forwarded
Headers for source &
destination addresses
Routing at message
switches
Connectionless

Message Switching Delay


Source

Switch 1

Switch 2

Destination

t
t
Delay
Minimum delay = 3 + 3T

Additional queueing delays possible at each link

Long Messages vs. Packets


1 Mbit
message

source
BER=p=10-6

dest

BER=10-6

How many bits need to be transmitted to deliver message?

Approach 1: send 1 Mbit


message
Probability message
arrives correctly
6 10 6

Pc (1 10 )

10 610 6

e 1 1 / 3

On average it takes about


3 transmissions/hop
Total # bits transmitted 6
Mbits

Approach 2: send 10
100-kbit packets
Probability packet arrives
correctly
5

Pc (1 10 6 )10 e 10 10 e 0.1 0.9

On average it takes about


1.1 transmissions/hop
Total # bits transmitted
2.2 Mbits

Packet Switching - Datagram

Messages broken into smaller


units (packets)
Source & destination
addresses in packet header
Connectionless, packets
routed independently
(datagram)
Packet may arrive out of
order
Pipelining of packets across
network can reduce delay,
increase throughput
Lower delay that message
switching, suitable for
interactive traffic

Packet 1
Packet 1
Packet 2

Packet 2
Packet 2

Packet Switching Delay


Assume three packets corresponding to one message
traverse same path
t
1

t
1

t
1

Delay

Minimum Delay = 3 + 5(T/3) (single path assumed)


Additional queueing delays possible at each link
Packet pipelining enables message to arrive sooner

Delay for k-Packet Message over L


Hops
Source
Switch 1
Switch 2

t
1

t
1

t
1

Destination

t
L hops

3 hops
3 + 2(T/3) first bit received

L + (L-1)P first bit received

3 + 3(T/3) first bit released

L + LP first bit released

3 + 5 (T/3) last bit released

L + LP + (k-1)P last bit released


where T = k P

Routing Tables in Datagram


Networks
Destination
address

Output
port

0785

1345

12

1566

2458

12

Route determined by table


lookup
Routing decision involves
finding next hop in route to
given destination
Routing table has an entry
for each destination
specifying output port that
leads to next hop
Size of table becomes
impractical for very large
number of destinations

Example: Internet Routing


Internet

protocol uses datagram packet


switching across networks

Networks are treated as data links

Hosts

have two-port IP address:

Network address + Host address

Routers

do table lookup on network address

This reduces size of routing table

In

addition, network addresses are assigned


so that they can also be aggregated

Discussed as CIDR in Chapter 8

Packet Switching Virtual Circuit


Packet

Packet
Packet
Packet
Virtual circuit

Call set-up phase sets up pointers in fixed path along network


All packets for a connection follow the same path
Abbreviated header identifies connection on each link
Packets queue for transmission
Variable bit rates possible, negotiated during call set-up
Delays variable, cannot be less than circuit switching

Connection Setup
Connect
request
Connect
confirm

SW
1

Connect
request
Connect
confirm

SW
2

SW
n

Connect
request
Connect
confirm

Signaling messages propagate as route is selected


Signaling messages identify connection and setup tables in
switches
Typically a connection is identified by a local tag, Virtual
Circuit Identifier (VCI)
Each switch only needs to know how to relate an incoming tag
in one input to an outgoing tag in the corresponding output
Once tables are setup, packets can flow along path

Connection Setup Delay


t

Connect
request

CC

CR

CC
CR

Connect
confirm

3
1

Release

t
t

Connection setup delay is incurred before any packet


can be transferred
Delay is acceptable for sustained transfer of large
number of packets
This delay may be unacceptably high if only a few
packets are being transferred

Virtual Circuit Forwarding Tables


Input
VCI

Output
port

Output
VCI

12

13

44

15

15

23

27

13

16

58

34

Each input port of packet


switch has a forwarding
table
Lookup entry for VCI of
incoming packet
Determine output port (next
hop) and insert VCI for next
link
Very high speeds are
possible
Table can also include
priority or other information
about how packet should be
treated

Cut-Through switching
Source
Switch 1
Switch 2

t
2

t
2

t
1

Destination

3
2

t
Minimum delay = 3 + T

Some networks perform error checking on header only,


so packet can be forwarded as soon as header is
received & processed
Delays reduced further with cut-through switching

Message vs. Packet Minimum


Delay

Message:
L + LT

= L + (L 1) T + T

Packet
L + L P + (k 1) P = L + (L 1) P + T

Cut-Through Packet (Immediate forwarding after


header)
= L+ T
Above neglect header processing delays

Example: ATM Networks


All

information mapped into short fixed-length


packets called cells
Connections set up across network

Virtual circuits established across networks


Tables setup at ATM switches

Several

types of network services offered

Constant bit rate connections


Variable bit rate connections

Packet-Switching
Networks
Routing in Packet Networks

Routing in Packet Networks


1

3
6
4

Three

Node
(switch or router)

possible (loopfree) routes from 1 to 6:

1-3-6, 1-4-5-6, 1-2-5-6

Which

is best?

Min delay? Min hop? Max bandwidth? Min cost?


Max reliability?

Creating the Routing Tables


Need

information on state of links

Link up/down; congested; delay or other metrics

Need

to distribute link state information using a


routing protocol

What information is exchanged? How often?


Exchange with neighbors; Broadcast or flood

Need

to compute routes based on information

Single metric; multiple metrics


Single route; alternate routes

Routing Algorithm Requirements

Responsiveness to changes

Optimality

Resource utilization, path length

Robustness

Topology or bandwidth changes, congestion


Rapid convergence of routers to consistent set of routes
Freedom from persistent loops

Continues working under high load, congestion, faults, equipment failures, incorrect implementations

Simplicity

Efficient software implementation, reasonable processing load

Routing in Virtual-Circuit Packet


Networks
2

1
A

Host

VCI

Switch or router

5
5
2

2
6

8
6

3
C

Route determined during connection setup


Tables in switches implement forwarding that
realizes selected route

Routing Tables in VC Packet


Networks
Node 3
Node 1
Incoming
Node VCI
A
1
A
5
3
2
3
3

Outgoing
Node VCI
3
2
3
3
A
1
A
5

Incoming
Node VCI
1
2
1
3
4
2
6
7
6
1
4
4

Outgoing
Node VCI
6
7
4
4
6
1
1
2
4
2
1
3

Node 6
Incoming
Node VCI
3
7
3
1
B
5
B
8

Outgoing
Node VCI
B
8
B
5
3
1
3
7

Node 4

Node 2
Incoming
Node VCI
C
6
4
3

Outgoing
Node VCI
4
3
C
6

Incoming
Node VCI
2
3
3
4
3
2
5
5

Outgoing
Node VCI
3
2
5
5
2
3
3
4

Node 5
Incoming
Node VCI
4
5
D
2

Example: VCI from A to D

From A & VCI 5 3 & VCI 3 4 & VCI 4


5 & VCI 5 D & VCI 2

Outgoing
Node VCI
D
2
4
5

Routing Tables in Datagram


Packet Networks
Node 3
Node 1
Destination
Next node
2
2
3
3
4
4
5
2
6
3

Destination
1
3
4
5
6

Node 2
Next node
1
1
4
5
5

Destination
1
2
4
5
6

Next node
1
4
4
6
6

Destination
1
2
3
5
6

Node 4
Next node
1
2
3
5
3

Node 6
Destination
Next node
1
3
2
5
3
3
4
3
5
5

Node 5
Destination
Next node
1
4
2
2
3
4
4
4
6
6

Non-Hierarchical Addresses and


Routing
0000
0111
1010
1101

0011
0110
1001
1100

No

4
3

0001
0100
1011
1110

R1
0000
0111
1010

1
1
1

R2
0001
0100
1011

5
4
4
4

0011
0101
1000
1111

relationship between addresses & routing


proximity
Routing tables require 16 entries each

Hierarchical Addresses and


Routing
0000
0001
0010
0011

1000
1001
1010
1011

Prefix

4
3

0100
0101
0110
0111

R1
00
01
10
11

1
3
2
3

R2
00
01
10
11

3
4
3
5

5
1100
1101
1110
1111

indicates network where host is


attached
Routing tables require 4 entries each

Specialized Routing
Flooding

Useful in starting up network


Useful in propagating information to all nodes

Deflection

Routing

Fixed, preset routing procedure


No route synthesis

Flooding
Send a packet to all nodes in a network
No routing tables available
Need to broadcast packet to all nodes (e.g. to
propagate link state information)
Approach
Send packet on all ports except one where it arrived
Exponential growth in packet transmissions

3
6

Flooding is initiated from Node 1: Hop 1 transmissions

3
6

Flooding is initiated from Node 1: Hop 2 transmissions

3
6

Flooding is initiated from Node 1: Hop 3 transmissions

Limited Flooding
Time-to-Live

field in each packet limits


number of hops to certain diameter
Each switch adds its ID before flooding;
discards repeats
Source puts sequence number in each
packet; switches records source address and
sequence number and discards repeats

Deflection Routing

Network nodes forward packets to preferred port


If preferred port busy, deflect packet to another port
Works well with regular topologies

Manhattan street network


Rectangular array of nodes
Nodes designated (i,j)
Rows alternate as one-way streets
Columns alternate as one-way avenues

Bufferless operation is possible

Proposed for optical packet networks


All-optical buffering currently not viable

0,0

0,1

0,2

0,3

1,0

1,1

1,2

1,3

2,0

2,1

2,2

2,3

3,0

3,1

3,2

3,3

Tunnel from
last column to
first column or
vice versa

Example: Node (0,2)(1,0)


busy
0,0

0,1

0,2

0,3

1,0

1,1

1,2

1,3

2,0

2,1

2,2

2,3

3,0

3,1

3,2

3,3

Packet-Switching
Networks
Shortest Path Routing

Shortest Paths & Routing


Many

possible paths connect any given


source and to any given destination
Routing involves the selection of the path to
be used to accomplish a given transfer
Typically it is possible to attach a cost or
distance to a link connecting two nodes
Routing can then be posed as a shortest path
problem

Routing Metrics
Means for measuring desirability of a path
Path Length = sum of costs or distances
Possible metrics

Hop count: rough measure of resources used


Reliability: link availability; BER
Delay: sum of delays along path; complex & dynamic
Bandwidth: available capacity in a path
Load: Link & router utilization along path
Cost: $$$

Shortest Path Approaches


Distance Vector Protocols
Neighbors exchange list of distances to destinations
Best next-hop determined for each destination
Ford-Fulkerson (distributed) shortest path algorithm
Link State Protocols
Link state information flooded to all routers
Routers have complete topology information
Shortest path (& hence next hop) calculated
Dijkstra (centralized) shortest path algorithm

Distance Vector
Do you know the way to San Jose?
Sa
nJ
os
e

San Jose 392


29
4

n
Sa

San Jose 596

se
Jo
0
25

Distance Vector
Local Signpost
Direction
Distance
Routing Table
For each destination list:
Next Node
dest next dist
Distance

Table Synthesis
Neighbors exchange
table entries
Determine current best
next hop
Inform neighbors

Periodically
After changes

Shortest Path to SJ
Focus on how nodes find their shortest
path to a given destination node, i.e. SJ

Dj
Cij

i
Di

Sa
n
Jo
se

If Di is the shortest distance to SJ from i


and if j is a neighbor on the shortest path,
then Di = Cij + Dj

But we dont know the shortest


paths
i only has local info
from neighbors
Dj'

Sa
n
Jo
se

j'
Cij'

i
Di

Cij
Cij

j"

Dj

Dj"

Pick current
shortest path

Why Distance Vector Works SJ sends


accurate info

3 Hops
From SJ

2 Hops
From SJ

1 Hop
From SJ

Accurate info about SJ


ripples across network,
Shortest Path Converges

Sa
n
Jo
se
Hop-1 nodes
calculate current
(next hop, dist), &
send to neighbors

Bellman-Ford Algorithm

Consider computations for one destination d


Initialization
Each node table has 1 row for destination d
Distance of node d to itself is zero: Dd=0
Distance of other node j to d is infinite: Dj=, for j d
Next hop node nj = -1 to indicate not yet defined for j d
Send Step
Send new distance vector to immediate neighbors across local link
Receive Step
At node j, find the next hop that gives the minimum distance to d,

Minj

{ Cij + Dj }

Replace old (nj, Dj(d)) by new (nj*, Dj*(d)) if new next node or distance

Go to send step

Bellman-Ford Algorithm

Now consider parallel computations for all destinations d


Initialization
Each node has 1 row for each destination d
Distance of node d to itself is zero: Dd(d)=0
Distance of other node j to d is infinite: Dj(d)= , for j d
Next node nj = -1 since not yet defined
Send Step
Send new distance vector to immediate neighbors across local link
Receive Step
For each destination d, find the next hop that gives the minimum
distance to d,

Minj { Cij+ Dj(d) }

Replace old (nj, Di(d)) by new (nj*, Dj*(d)) if new next node or distance
found

Go to send step

Iteration

Node 1

Node 2

Node 3

Node 4

Node 5

Initial

(-1, )

(-1, )

(-1, )

(-1, )

(-1, )

1
2
3
Table entry
@ node 3
for dest SJ

Table entry
@ node 1
for dest SJ
2

1
5

San
Jose

4
3

Iteration

Node 1

Node 2

Node 3

Node 4

Node 5

Initial

(-1, )

(-1, )

(-1, )

(-1, )

(-1, )

(-1, )

(-1, )

(6,1)

(-1, )

(6,2)

2
3
D3=D6+1
n3=6
D6=0

3 1

1
5

4
3

5
4

D5=D6+2
n5=6

D6=0

San
Jose

Iteration

Node 1

Node 2

Node 3

Node 4

Node 5

Initial

(-1, )

(-1, )

(-1, )

(-1, )

(-1, )

(-1, )

(-1, )

(6, 1)

(-1, )

(6,2)

(3,3)

(5,6)

(6, 1)

(3,3)

(6,2)

1
5

4
3

San
Jose

Iteration

Node 1

Node 2

Node 3

Node 4

Node 5

Initial

(-1, )

(-1, )

(-1, )

(-1, )

(-1, )

(-1, )

(-1, )

(6, 1)

(-1, )

(6,2)

(3,3)

(5,6)

(6, 1)

(3,3)

(6,2)

(3,3)

(4,4)

(6, 1)

(3,3)

(6,2)

1
5

4
3

6 4

San
Jose

Iteration

Node 1

Node 2

Node 3

Node 4

Node 5

Initial

(3,3)

(4,4)

(6, 1)

(3,3)

(6,2)

(3,3)

(4,4)

(4, 5)

(3,3)

(6,2)

2
3
1 5

1
5

4
3

San
Jose

Network disconnected; Loop created between nodes 3 and 4

Iteration

Node 1

Node 2

Node 3

Node 4

Node 5

Initial

(3,3)

(4,4)

(6, 1)

(3,3)

(6,2)

(3,3)

(4,4)

(4, 5)

(3,3)

(6,2)

(3,7)

(4,4)

(4, 5)

(5,5)

(6,2)

37

1
5

53

San
Jose

Node 4 could have chosen 2 as next node because of tie

Iteration

Node 1

Node 2

Node 3

Node 4

Node 5

Initial

(3,3)

(4,4)

(6, 1)

(3,3)

(6,2)

(3,3)

(4,4)

(4, 5)

(3,3)

(6,2)

(3,7)

(4,4)

(4, 5)

(5,5)

(6,2)

(3,7)

(4,6)

(4, 7)

(5,5)

(6,2)

5 7

1
5

46

5
4

San
Jose

Node 2 could have chosen 5 as next node because of tie

Iteration

Node 1

Node 2

Node 3

Node 4

Node 5

(3,3)

(4,4)

(4, 5)

(3,3)

(6,2)

(3,7)

(4,4)

(4, 5)

(2,5)

(6,2)

(3,7)

(4,6)

(4, 7)

(5,5)

(6,2)

(2,9)

(4,6)

(4, 7)

(5,5)

(6,2)

79

1
5

7
1

4
3

San
Jose

Node 1 could have chose 3 as next node because of tie

Counting to Infinity Problem


(a)

(b)

1
1

2
2

1
1

3
3

Nodes believe best


path is through each
other
(Destination is node 4)

Update

Node 1

Node 2

Node 3

Before break

(2,3)

(3,2)

(4, 1)

After break

(2,3)

(3,2)

(2,3)

(2,3)

(3,4)

(2,3)

(2,5)

(3,4)

(2,5)

(2,5)

(3,6)

(2,5)

(2,7)

(3,6)

(2,7)

(2,7)

(3,8)

(2,7)

Problem: Bad News Travels


Slowly
Remedies
Split Horizon

Do not report route to a destination to the


neighbor from which route was learned

Poisoned Reverse

Report route to a destination to the neighbor


from which route was learned, but with infinite
distance
Breaks erroneous direct loops immediately
Does not work on some indirect loops

Split Horizon with Poison Reverse


(a)

(b)

1
1

2
2

1
1

3
3

1
X

4
4

Nodes believe best


path is through
each other

Update

Node 1

Node 2

Node 3

Before break

(2, 3)

(3, 2)

(4, 1)

After break

(2, 3)

(3, 2)

(-1, )

Node 2 advertizes its route to 4 to


node 3 as having distance infinity;
node 3 finds there is no route to 4

(2, 3)

(-1, )

(-1, )

Node 1 advertizes its route to 4 to


node 2 as having distance infinity;
node 2 finds there is no route to 4

(-1, )

(-1, )

(-1, )

Node 1 finds there is no route to 4

Link-State Algorithm

Basic idea: two step procedure

Each source node gets a map of all nodes and link metrics (link
state) of the entire network
Find the shortest path on the map from the source node to all
destination nodes

Broadcast of link-state information

Every node i in the network broadcasts to every other node in the


network:

IDs

of its neighbors: Ni=set of neighbors of

i
Distances to its neighbors: {Cij | j Ni}

Flooding is a popular method of broadcasting packets

Dijkstra Algorithm: Finding


shortest paths in order
Find shortest paths from
source s to all other
destinations

w
'
s

Closest node to s is 1 hop away


2nd closest node to s is 1 hop
away from s or w
3rd closest node to s is 1 hop
away from s, w, or x

x
w
"

z'
x'

Dijkstras algorithm

N: set of nodes for which shortest path already found


Initialization: (Start with source node s)

N = {s}, Ds = 0, s is distance zero from itself

Dj=Csj for all j s, distances of directly-connected neighbors

Step A: (Find next closest node i)

Find i N such that


Di = min Dj for j N
Add i to N
If N contains all the nodes, stop

Step B: (update minimum costs)

For each node j N


Dj = min (Dj, Di+Cij)

Go to Step A

Minimum distance from s to


j through node i in N

Execution of Dijkstras algorithm


2

5
4

1
2
4

2
5

4
3

1
2

3
2

2
5

Iteration

D2

D3

D4

D5

D6

Initial

{1}

{1,3}

{1,2,3}

{1,2,3,6}

{1,2,3,4,6}

{1,2,3,4,5,6}

Shortest Paths in Dijkstras


Algorithm
2
2
5

2
2
5

2
4

2
4

4
4

2
1

5
3

2
4

Reaction to Failure

If a link fails,
Router sets link distance to infinity & floods the
network with an update packet
All routers immediately update their link database &
recalculate their shortest paths
Recovery very quick
But watch out for old update messages
Add time stamp or sequence # to each update
message
Check whether each received update message is new
If new, add it to database and broadcast
If older, send update message on arriving link

Why is Link State Better?


Fast,

loopless convergence
Support for precise metrics, and multiple
metrics if necessary (throughput, delay, cost,
reliability)
Support for multiple paths to a destination
algorithm

can be modified to find best two paths

Source Routing

Source host selects path that is to be followed by a


packet

Strict: sequence of nodes in path inserted into header


Loose: subsequence of nodes in path specified

Intermediate switches read next-hop address and


remove address
Source host needs link state information or access
to a route server
Source routing allows the host to control the paths
that its information traverses in the network
Potentially the means for customers to select what
service providers they use

Example
3,6,B
1,3,6,B

6,B

3
6

A
4

Source host
2

Destination host

You might also like