Transcript EECC694 - Shaaban

The OSI Reference Model
Network
Layer
EECC694 - Shaaban
#1 lec #7 Spring2000 3-28-2000
The Subnet
A point-to-point network interconnecting fast specialized computers
(routers or switches ) dedicated to packet routing using very high
bandwidth links forming the backbone of the entire network.
Operation of the subnet is the concern of the network layer.
EECC694 - Shaaban
#2 lec #7 Spring2000 3-28-2000
The Network Layer
• Concerned with getting packets from the source all the way to the
destination: Routing through the subnet, load balancing, congestion
control.
• Protocol Data Unit (PDU) for network layer protocols = packet
• Types of network services to the transport layer:
– Connectionless: Each packet carries full destination address.
– Connection-oriented:
• Connection is set up between network layer processes on the
sending and receiving sides.
• The connection is given a special identifier until all data has been
sent.
• Internal organization of the network layer (in the subnet):
– Datagram: Packets are sent and routed independently with each
carrying the full destination address (TCP/IP).
– Virtual circuit: A virtual circuit is set up to the destination using
a
circuit number stored in tables in routers along the way. Packets only
carry the virtual circuit number. All packets follow the same route
(cells in the case of ATM networks).
EECC694 - Shaaban
#3 lec #7 Spring2000 3-28-2000
Virtual Circuit
Vs.
Datagram Subnets
EECC694 - Shaaban
#4 lec #7 Spring2000 3-28-2000
Service And Subnet
Structure Combinations
Or TCP
Over
IP
Over
ATM
EECC694 - Shaaban
#5 lec #7 Spring2000 3-28-2000
Placement of Network Layer
Routing Process
Two adjacent subnet routers shown.
EECC694 - Shaaban
#6 lec #7 Spring2000 3-28-2000
Routing Algorithms
To decide which output line an incoming packet should be
transmitted on to reach its destination.
• Static Routing (Non-adaptive algorithms):
– Shortest path routing:
• Build a graph of the subnet with each node representing a router
and each arc representing a communication link.
• The weight on the arcs represents: a function of distance,
bandwidth, communication costs, mean queue length, and other
performance factors.
• Several algorithms exist including Dijkstra’s shortest path
algorithm.
– Selective flooding: Send the packet on all output lines going in the
right direction to the destination.
– Flow-based routing: Based on known capacity and link loads.
EECC694 - Shaaban
#7 lec #7 Spring2000 3-28-2000
Static Routing: Shortest Path Routing
• First five steps of an example using Dijktra’s algorithm
EECC694 - Shaaban
#8 lec #7 Spring2000 3-28-2000
Static Routing: Flow-Based Routing
• A routing matrix is constructed; used when the mean data
flow in network links is known and stable.
• Given: Capacity matrix Cij, Traffic matrix Fij,
• Mean delay at each line T= 1/(mC -l)
mC line capacity packet/sec
l traffic packet/sec
A subnet with link
capacities given in kbps
The traffic in packets/sec
and routing table
EECC694 - Shaaban
#9 lec #7 Spring2000 3-28-2000
Flow-Based Routing Calculation Example
Flow-based routing analysis example for network on previous page, assuming:
Mean packet size = 800 bits.
Reverse traffic is the same as forward traffic
weighti = flow in link i / total flow in the subnet
Mean delay per packet =  weighti x Ti = 86 msec in above example
Goal find a flow with minimum mean delay per packet.
EECC694 - Shaaban
#10 lec #7 Spring2000 3-28-2000
•
•
•
Dynamic Routing: Distance Vector
Each router maintains a table with one
entry for each router in the subnet
including the preferred outgoing link,
and an estimate of time or distance to
the destination router.
Neighbor router table entries are
gathered by sending ECHO packets
which are sent back with a time stamp.
Each router exchanges its table of
estimates with its neighbors; the best
estimate is chosen.
Used in ARPANET
until 1979
EECC694 - Shaaban
#11 lec #7 Spring2000 3-28-2000
Distance Vector
Routing:
Count-to-Infinity
Problem
Link AB Initially down
This is the main reason Distance
Vector Routing has been mostly
abandoned.
Link AB Initially Up
EECC694 - Shaaban
#12 lec #7 Spring2000 3-28-2000
Dynamic Routing: Link State Routing
• Resolves Count-to-Infinity Problem present in Distance Vector Routing.
• Variants of link state routing are widely used.
• Each router using Link State Routing must:
– Discover its neighbors and know their network address.
– Measure the delay or cost to each of the neighbors using ECHO packets.
– Construct a link state packet to include what it learned about its
neighbors including the age of the information.
– Send the link state packet to all other routers in the subnet.
– Compute the shortest path to every other router based on information
gathered from all link state packets (Dijksra’a algorithm may be used
here).
EECC694 - Shaaban
#13 lec #7 Spring2000 3-28-2000
Hierarchical Routing
•
•
•
The subnet is divided into several regions of routers.
Each router maintains a table of routing information to routers in its region only.
Packets destined to another region are routed to a designated router in that
region.
A two-level Hierarchical Routing Example:
Optimum number of hierarchy levels:
For a subnet of N routers:
Optimum # of levels = ln N
Total # of table entries = e ln N
EECC694 - Shaaban
#14 lec #7 Spring2000 3-28-2000