Intra-AS Routing/Interior Gateway Protocols (IGP)
Most common IGPs:
RIP: Routing Information Protocol (lower-tier ISPs and
Copyright By PowCoder代写 加微信 powcoder
Enterprise networks)
OSPF: Open Shortest Path First (upper-tier ISPs)
IGRP: Interior Gateway Routing Protocol (Cisco proprietary)
Network Layer – part 3 2
RIP ( Routing Information Protocol)
RFC1058 Included in (Berkeley Software Distribution) BSD-UNIX
Distance vector algorithm
Distribution in 1982
Still in widespread use today
Distance metric:
Hop – no. of subnets traversed along the shortest path from Source Router to Destination Subnet, including the Destination Subnet.
Max. number of hops = 15 hops = (AS < 15 hops in diameter)
Due to the count-to-infinity problem of DV algorithm
Can you guess why?
Distance vectors: exchange routing updates via Response
Message (also called advertisement) every 30 sec
Each advertisement: route to up to 25 destination subnets
within the AS, including the sender’s distance from each of
Network Layer – part 3 3
RIP (Routing Information Protocol)
x -- 1 ... ....
Routing table of Router D
Destination Subnet Next Router Num. of hops to dest.
wA2 yB2 zB7
Network Layer – part 3 4
RIP (Routing Information Protocol)
xD By Routing table in Router D
Destination Subnet Next Router
Num. of hops to dest.
Router A has a shorter path to Z!
x -- 1 ... ... ....
30 secs. later..
D receives an advertisement from Router A )
Destination Subnet Next Router Num. of hops to dest.
x -- 1 ... ... ....
Network Layer – part 3 5
RIP (Routing Information Protocol)
-- 1 ... ....
xD By Routing table in Router D
Destination Subnet
Next Router Num. of hops to dest.
Destination Subnet
Next Router Num. of hops to dest.
z A 4 + c(D,A)
Advertisement from Router A
Router D updates its entry for destination Z
x -- 1 ... ... ....
Network Layer – part 3 6
RIP: Link Failure and Recovery
If no advertisement is heard from a neighbour after 180 sec --> then that neighbour/link is declared dead
Modifies routing table – routes via neighbour invalidated
new advertisements sent to neighbours
neighbours in turn send out new advertisements (if tables changed) link failure info quickly propagates to entire net
poisoned reverse used to prevent ping-pong loops
Network Layer – part 3 7
Routing Info Protocol (RIP) Routing Table processing
In a UNIX workstation serving as a router, the RIP routing tables are managed by an application-level process called route-d (daemon)
advertisements sent in UDP packets, periodically
Able to manipulate routing tables within the UNIX kernel
http://www.quagga.net/
Network Layer – part 3 8
via UDP, port 520
OSPF (Open Shortest Path First)
“Open” means publicly available
Uses Link-State algorithm to find the shortest path to all subnets.
LS packet dissemination
Topology map at each node
Route computation using Dijkstra’s algorithm
Broadcasts information to all not just neighboring routers
Router broadcasts link’s state periodically (at least every 30 min.)
Advertisements disseminated to entire AS (via flooding) Carried in OSPF messages directly over IP (rather than TCP or
UDP) with upper-layer protocol of 89
Note that without reliance on TCP, reliable data transfer functionality needs to be provided by the OSPF protocol itself.
OSPF Protocol Functionalities: reliable data transfer, link-state broadcast, check for Network Layer – part 3 9
links operability, extraction of neighboring router’s database of network-wide link state
OSPF advanced features (not in RIP)
Advanced Features
Allow only trusted routers
Security: all OSPF messages authenticated (to prevent malicious intrusion)
Multiple same-cost paths allowed (only one path in RIP) Integrated uni- and multicast routing support:
Multicast OSPF (MOSPF) uses same topology data base as OSPF
Hierarchical OSPF in large domains.
Most significant advancement! It has the ability to structure an
autonomous system hierarchically
Network Layer – part 3 10
Hierarchical Open Shortest Path First
OSPF routing
OSPF routing
routing OSPF
Network Layer – part 3 11
Hierarchical OSPF
Two-level hierarchy: local area, backbone.
Link-state advertisements are sent only within an area
each node has detailed area topology; but only knows direction (shortest path) to nets in other areas.
Each area runs its own OSPF link-state routing algorithm
Area border routers: responsible for routing packets
outside the area.
Backbone routers: run OSPF routing limited to backbone.
Boundary routers: connect to other ASs.
Network Layer – part 3 12
IGRP (Interior Gateway Routing Protocol)
CISCO proprietary; successor of RIP (mid 80s)
Uses the Distance Vector algorithm, like RIP
several cost metrics (delay, bandwidth, reliability, load, etc.)
uses TCP to exchange routing updates
Loop-free routing via Distributed Updating Alg. (DUAL) based on diffused computation
Network Layer – part 3 13
Customer-Provider Routing Relationships
The global Internet consists of Autonomous Systems (AS) interconnected with each other:
A,B,C are provider networks
w, x, y are customers of provider networks
x is dual-homed; attached to two provider networks x does not want to carry traffic from B to C,
so x will not advertise to B a route to C
Stub AS: small corporation
Group of routers
Transit AS: backbone provider networks
Multihomed AS:
large corporation
Network Layer – part 3 15
Customer-Provider Routing Relationships
The global Internet consists of Autonomous Systems
(AS) interconnected with each other:
A,B,C are provider networks
w, x, y are customers of provider networks
x is dual-homed; attached to two provider networks x does not want to carry traffic from B to C,
Advertises to its
so x will not advertise to B a route to C
All traffic entering must be destined for w, all traffic leaving must have originated from w
Transit AS: backbone
provider networks B
Multihomed AS:
Stub AS: small corporation
Group of routers
Stub AS must be prevented from forwarding traffic between Transit ASs using Selective Route Advertisement Policy
Network Layer – part 3 16
neighbors that it has no paths to any other destinations except itself
large corporation
Customer-Provider Routing Policy Example
A advertises to B, the path Aw
B advertises to x, the path BAw
B does not advertise to C, the path BAw
• B gets no “revenue” for routing CBAw, since neither w nor C are B’s
• BwantstoforceCtoroutetow,viaA
• B wants to route only to/from its customers!
Network Layer – part 3 17
Internet AS Hierarchy
AS border (exterior gateway) routers
AS interior (gateway) routers
How to handle external-AS destinations?
Network Layer – part 3 18
Routing in the Internet
Two-level routing:
Intra-AS: administrator is responsible for choice Inter-AS: unique standard
Allows each subnet to advertise its existence to the rest of the Internet
provides each AS a means to:
• obtain subnet reachability information
(i.e. via one of its neighboring AS)
• propagate the reachability information to all
Border Gateway Protocol (BGP4)
de facto standard inter-AS routing protocol in today’s Internet (since 1994)
routers internal to the AS
• determine “good” routes to subnets based on the
reachability information and on AS policy.
Network Layer – part 3 19
Interconnected Autonomous Systems
3c 3a 3b AS3
1c 2a 1a1d 1bAS1
How to handle external-AS destinations?
Network Layer 4-20
Intra-AS Routing algorithm
Inter-AS Routing algorithm
forwarding table configured by both intra- and inter-AS routing algorithms
Forwarding table
intra-AS sets entries for internal dests.
inter-AS & intra-As sets entries for external dests.
Inter-AS tasks
suppose router in AS1 receives datagram destined outside of AS1:
other networks
To which gateway router, should the packet be forwarded to?
other networks
Datagram destined to AS5
A packet arrives at router 1d, and it is destined to AS5.
Network Layer 4-21
Inter-AS tasks
suppose router in AS1 receives datagram destined outside of AS1:
other networks
router should forward packet to gateway router, but which one?
2. propagate this reachability info to all routers in AS1
other networks
1. learn which destinations are reachable through AS2, which through AS3
job of inter-AS routing!
Network Layer 4-22
Example: Setting forwarding table in router 1d
(Using inter-AS protocol)
suppose AS1 learns that subnet x reachable via AS3 (gateway 1c) but not via AS2.
inter-AS protocol propagates reachability info to all internal routers
other networks
other networks
Network Layer 4-23
Example: Setting forwarding table in router 1d
(Using inter-AS protocol)
(Using intra-AS protocol)
suppose AS1 learns that subnet x reachable via AS3 (gateway 1c) but not via AS2.
router 1d determines from intra-AS routing info that its interface i is on the least cost path to 1c.
inter-AS protocol propagates reachability info to all internal routers
installs forwarding table entry (x,i)
other networks
other networks
Network Layer 4-24
Example: Choosing among multiple ASes now suppose AS1 learns from inter-AS protocol that
other networks
subnet x is reachable both from AS3 and from AS2.
to configure forwarding table, router 1d must determine which gateway it should forward packets towards subnet x
Solution: hot potato routing: send packet towards closest of two routers.
other networks
Network Layer 4-25
Summary: Adding an Outside-AS Destination in a Router’s Forwarding Table
Learn from an Inter-AS protocol that subnet x is reachable via multiple gateways.
Use intra-AS routing protocol to determine least-cost paths to each of the gateways.
Determine from the forwarding table the interface i that leads towards the least-cost gateway. Enter (x, i) in the forwarding table
“Hot-potato routing”: Pick the gateway with the least-cost path.
Network Layer – part 3 26
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com