CS代考 RFC1058  Included in (Berkeley Software Distribution) BSD-UNIX

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