DOC PREVIEW
U of I CS 438 - Routing in the Internet

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1RoutingintheInternetLast Time Link-State routing protocol Broadcast all link state to all routers Run Dijkstra’s algorithm to find best paths Distance Vector routing protocol Distribute vector of current distances toall neighbors Update current distances based onneighbors’ inputsMP3 Implement LS and DV routingalgorithms Write a node that: Connects to some neighbors Monitors link quality Exchanges routing state information Computes (outputs) best routesTroll Network “troll” simulates an unreliablelink Drops packets Delays packets Reorders packets Garbles packets One troll per direction of a (logical) linkExample Topology123T1T2T3T4T5T6Setting Up Topology Node i on port 500i Troll i on port 600itroll -h localhost -i 5002 6001troll -h localhost -i 5001 6002troll -h localhost -i 5003 6003troll -h localhost -i 5001 6004troll -h localhost -i 5002 6005troll -h localhost -i 5003 6006node DV 5001 localhost 6001 L1 localhost 6003 L2node DV 5002 localhost 6002 L1 localhost 6006 L3node DV 5003 localhost 6004 L2 localhost 6005 L32Things to Keep in Mind Find a partner Teams of 1-2, suggest 2 Ask in class, on newsgroup Start early! Deal with loss, errors, dead links How do you detect dead links? Watch out for runaway broadcast Solve the count-to-infinity problemThis class Routing in the Internet Hierarchical routing RIP OSPF BGP Broadcast techniquesHierarchical Routingscale: with 200 milliondestinations: can’t store all dest’s inrouting tables! routing table exchangewould swamp links!administrative autonomy internet = network of networks each network admin maywant to control routing in itsown networkOur routing study thus far - idealization all routers identical network “flat”… not true in practiceHierarchical Routing aggregate routers intoregions, “autonomoussystems” (AS) routers in same ASrun same routingprotocol “intra-AS” routingprotocol routers in different AScan run different intra-AS routing protocolGateway router Direct link to routerin another AS3b1d3a1c2aAS3AS1AS21a2c2b1bIntra-ASRouting algorithmInter-ASRouting algorithmForwardingtable3cInterconnected ASes Forwarding table isconfigured by bothintra- and inter-ASrouting algorithm Intra-AS sets entriesfor internal dests Inter-AS & Intra-Assets entries for externaldests3b1d3a1c2aAS3AS1AS21a2c2b1b3cInter-AS tasks Suppose router in AS1receives datagram forwhich dest is outsideof AS1 Router should forwardpacket towards one ofthe gateway routers,but which one?AS1 needs:1. to learn which destsare reachable throughAS2 and whichthrough AS32. to propagate thisreachability info to allrouters in AS1Job of inter-AS routing!3Example: Setting forwarding table in router 1d Suppose AS1 learns (via inter-AS protocol) that subnet xis reachable via AS3 (gateway 1c) but not via AS2. Inter-AS protocol propagates reachability info to allinternal routers. Router 1d determines from intra-AS routing info that itsinterface I is on the least cost path to 1c. Puts in forwarding table entry (x,I).3b1d3a1c2aAS3AS1AS21a2c2b1b3cChoosing among multiple ASes Now suppose AS1 learns from the inter-AS protocolthat subnet x is reachable from AS3 and from AS2. To configure forwarding table, router 1d mustdetermine towards which gateway it should forwardpackets for dest x. This is also the job on inter-AS routing protocol!3b1d3a1c2aAS3AS1AS21a2c2b1b3cLearn from inter-AS protocol that subnet x is reachable via multiple gatewaysUse routing infofrom intra-ASprotocol todeterminecosts of least-costpaths to eachof the gatewaysHot potato routing:Choose thegatewaythat has thesmallest least costDetermine fromforwarding table the interface I that leads to least-cost gateway. Enter (x,I) in forwarding tableChoosing among multiple ASes Now suppose AS1 learns from the inter-AS protocolthat subnet x is reachable from AS3 and from AS2. To configure forwarding table, router 1d mustdetermine towards which gateway it should forwardpackets for dest x. This is also the job on inter-AS routing protocol! Hot potato routing: send packet towards closest of tworouters.Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit anddatagram networks 4.3 What’s inside arouter 4.4 IP: InternetProtocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in theInternet RIP OSPF BGP 4.7 Broadcast andmulticast routingIntra-AS Routing Also known as Interior Gateway Protocols(IGP) Most common Intra-AS routing protocols: RIP: Routing Information Protocol OSPF: Open Shortest Path First IGRP: Interior Gateway Routing Protocol(Cisco proprietary)Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit anddatagram networks 4.3 What’s inside arouter 4.4 IP: InternetProtocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in theInternet RIP OSPF BGP 4.7 Broadcast andmulticast routing4RIP ( Routing Information Protocol) Distance vector algorithm Included in BSD-UNIX Distribution in 1982 Distance metric: # of hops (max = 15 hops)DCBAuvwxyzdestination hops u 1 v 2 w 2 x 3 y 3 z 2 From router A to subsets:RIP advertisements Distance vectors: exchanged amongneighbors every 30 sec via ResponseMessage (also called advertisement) Each advertisement: list of up to 25destination nets within ASRIP: ExampleDestination Network Next Router Num. of hops to dest. w A 2y B 2 z B 7x -- 1…. …. ....wx yzACDBRouting table in DRIP: ExampleDestination Network Next Router Num. of hops to dest. w A 2y B 2 z B A 7 5x -- 1…. …. ....Routing table in Dwx yzACDB Dest Next hops w - 1 x - 1 z C 4 …. … ...Advertisementfrom A to DRIP: Link Failure and RecoveryIf no advertisement heard after 180 sec -->neighbor/link declared dead routes via neighbor invalidated new advertisements sent to neighbors neighbors in turn send out newadvertisements (if tables changed) link failure info quickly (?) propagates toentire net poison reverse used to prevent


View Full Document

U of I CS 438 - Routing in the Internet

Documents in this Course
Routing

Routing

5 pages

TCP

TCP

26 pages

TROLL

TROLL

3 pages

Load more
Download Routing in the Internet
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Routing in the Internet and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Routing in the Internet 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?