EECS 122 Introduction to Computer Networks Interdomain Routing Computer Science Division Department of Electrical Engineering and Computer Sciences University of California Berkeley Berkeley CA 94720 1776 Katz Stoica F04 Today s Lecture 2 17 18 19 10 11 6 7 Application Transport 14 15 16 8 9 21 22 23 25 Network IP Link Physical Katz Stoica F04 2 Distance Vector Link Cost Changes 7 loop 8 wait until A sees a link cost change to neighbor V 9 or until A receives update from neighbor V 10 if D A V changes by d 11 for all destinations Y through V do 12 D A Y D A Y d 13 else if update D V Y received from V 14 D A Y D A V D V Y 15 if there is a new minimum for destination Y 16 send D A Y to all neighbors 17 forever 1 4 A Node B D C N A 4 A D C N D C N D C N A 1 A A 1 A A 1 A C 1 B C 1 B C 1 B C 1 B Node C D C N A 5 B D C N D C N D C N A 5 B A 2 B A 2 B B 1 B B 1 B B 1 B B 1 B Link cost changes here B 50 1 C good news travels fast time Algorithm terminatesKatz Stoica F04 3 Distance Vector Count to Infinity Problem 7 loop 8 wait until A sees a link cost change to neighbor V 9 or until A receives update from neighbor V 10 if D A V changes by d 11 for all destinations Y through V do 12 D A Y D A Y d 13 else if update D V Y received from V 14 D A Y D A V D V Y 15 if there is a new minimum for destination Y 16 send D A Y to all neighbors 17 forever 60 4 A Node B D C N A 4 A D C N D C N D C N A 6 C A 6 C A 8 C C 1 B C 1 B C 1 B C 1 B Node C D C N A 5 B D C N D C N D C N A 5 B A 7 B A 2 B B 1 B B 1 B B 1 B B 1 B B 50 1 C bad news travels slowly time Link cost changes here recall from slide 24 that B also maintains shortest distance to A through C which is 6 Thus D B A becomes 6 Katz Stoica F04 4 Distance Vector Poisoned Reverse If C routes through B to get to A 60 C tells B its C s distance to A is infinite so B won t route to A via C Will this completely solve count to infinity problem A 60 A A 51 C A 51 C C 1 B C C 1 B C 1 B C 1 B C N D C N D C N B D C N C 50 A 60 A 1 N 1 D N C A B Node B D C N A 4 A C D 4 D C N Node C D C N A 5 B D C N D A 5 B A 50 A A 50 A A 50 A B 1 B B 1 B B B B 1 B 1 Link cost changes here B updates D B A 60 as C has advertised D C A B 1 B time Algorithm terminates Katz Stoica F04 5 Link State vs Distance Vector Per node message complexity LS O e messages e number of edges Robustness what happens if router malfunctions LS node can advertise incorrect link cost each node computes only its own table DV O d messages many times d is node s degree Complexity Convergence LS O n2 computation DV convergence time varies may be routing loops count to infinity problem DV node can advertise incorrect path cost each node s table used by others error propagate through network Katz Stoica F04 6 Are We Done We now know how to route scalably What more is there to do Katz Stoica F04 7 Issues We Haven t Addressed Scaling Addressing Router table size Structure Autonomy Policy Katz Stoica F04 8 Scaling Every router must be able to forward based on any destination IP address Given address it needs to know next hop table Naive Have an entry for each address There would be 10 8 entries Better Have an entry for a range of addresses But can t do this if addresses are assigned randomly Addresses allocation is a big deal Katz Stoica F04 9 Network Structure Large ISP Large ISP Stub Dial Up ISP Small ISP Stub Access Network Stub e Internet contains a large number of diverse network Katz Stoica F04 10 Autonomous Systems AS Internet is not a single network The Internet is a collection of networks each controlled by different administrations An autonomous system AS is a network under a single administrative control Katz Stoica F04 11 Implications ASs want to choose own local routing algorithm AS takes care of getting packets to from their own hosts Interdomain routing and Intradomain routing ASs want to choose own nonlocal routing policy Interdomain routing must accommodate this BGP is the current interdomain routing protocol Katz Stoica F04 12 Intradomain And Interdomain 44 B 66 B BGP 5 22 IntraDomain 4 3 3 7 8 6 RIP 13 13 11 2 10 OSPF IntraDomain 3 1 IGRP A IntraDomain 13 12 C Katz Stoica F04 13 Interconnection IP unifies network technologies allows any network to communicate with another BGP unifies network organizations ties them into a global Internet Katz Stoica F04 14 Outline Addressing BGP Katz Stoica F04 15 Assigning Addresses Ideally Host gets IP address from its organization or ISP Organization gets IP address block from ISP ISP gets address block from routing registry ARIN American Registry for Internet Numbers RIPE Reseaux IP Europeens APNIC Asia Pacific Network Information Center Each AS is assigned a 16 bit number 65536 total Currently 10 000 AS s in use Most stub so don t really need own number Katz Stoica F04 16 Original Addressing Scheme Class based addressing schemes 32 bits divided into 2 parts Class A Class B Class C 8 0 0 network 0 10 0 110 126 nets 16M hosts host 16 network 16K nets 65K hosts host 24 network host 2M nets 254 hosts Original Vision Route on network number All nodes with same net are directly connected Katz Stoica F04 17 Classless Interdomain Routing CIDR Introduced to solve two problems exhaustion of IP address space size and growth rate of routing table Katz Stoica F04 18 1 Address Space Exhaustion Example an organization needs 500 addresses A single class C address not enough 254 hosts Instead a class B address is allocated 65K hosts That s overkill a huge waste CIDR networks assigned on …
View Full Document
Unlocking...