Link‐State*Rou.ng*Reading:*Sec.ons*4.2*and*4.3.4*COS*461:*Computer*Networks*Spring*2009*(MW*1:30‐2:50*in*COS*105)*Michael*Freedman*Teaching*Assistants:*WyaN*Lloyd*and*Jeff*Terrace*hNp://www.cs.princeton.edu/courses/archive/spring09/cos461/*1!Goals*of*Today’s*Lecture*• Inside*a*router*– Control*plane:*rou.ng*protocols*– Data*plane:*packet*forwarding*• Path*selec.on*– Minimum‐hop*and*shortest‐path*rou.ng*– Dijkstra’s*algorithm*• Topology*change*– Using*beacons*to*detect*topology*changes*– Propaga.ng*topology*informa.on*• Rou.ng*protocol:*Open*Shortest*Path*First*2!What*is*Rou.ng?*• A*famous*quota.on*from*RFC*791**“A*name*indicates*what*we*seek.*An*address*indicates*where*it*is.*A*route*indicates*how*we*get*there.”*******‐‐*Jon*Postel*3!Rou.ng*vs.*Forwarding*• Rou.ng:*control*plane*– Compu.ng*paths*the*packets*will*follow*– Routers*talking*amongst*themselves*– Individual*router*crea,ng*a*forwarding*table*• Forwarding:*data*plane*– Direc.ng*a*data*packet*to*an*outgoing*link*– Individual*router*using*a*forwarding*table*4!Data*and*Control*Planes*5!Switching Fabric Processor Line card Line card Line card Line card Line card Line card data plane!control plane!Router*Physical*Layout*6!Juniper T series Cisco 12000 Switch LinecardsLine*Cards*(Interface*Cards,*Adaptors)*• Interfacing**– Physical*link*– Switching*fabric*• Packet*handling*– Packet*forwarding*– Decrement*.me‐to‐live*– Buffer*management*– Link*scheduling*– Packet*filtering*– Rate*limi.ng*– Packet*marking*– Measurement*7!to/from link to/from switch lookup Receive TransmitSwitching*Fabric*• Deliver*packet*inside*the*router*– From*incoming*interface*to*outgoing*interface*– A*small*network*in*and*of*itself*• Must*operate*ver y*quickly*– Mul.ple*packets*going*to*same*outgoing*interface*– Switch*scheduling*to*match*inputs*to*outputs*• Implementa.on*techniques*– Bus,*crossbar,*interconnec.on*network,*…*– Running*at*a*faster*speed*(e.g.,*2X)*than*links*– Dividing*variable‐length*packets*into*fixed‐size*cells*8!Packet*Switching*9!R1 Link 1 Link 2 Link 3 Link 4 Link 1, ingress Link 1, egress Link 2, ingress Link 2, egress Link 3, ingress Link 3, egress Link 4, ingress Link 4, egress Choose Egress Choose Egress Choose Egress Choose Egress “4” “4”Router*Processor*• So‐called*“Loopback”*interface*– IP*address*of*the*CPU*on*the*router*• Interface*to*network*administrators*– Command‐line*interface*for*configura.on*– Transmission*of*measurement*sta.s.cs**• Handling*of*special*data*packets*– Packets*with*IP*op.ons*enabled*– Packets*with*expired*Time‐To‐Live*field*• Control‐plane*soiware*– Implementa.on*of*the*rou.ng*protocols*– Crea.on*of*forwarding*table*for*the*line*cards*10!Where*do*Forwarding*Tables*Come*From?*• Routers*have*forwarding*tables*– Map*IP*prefix*to*outgoing*link(s)*• Entries*can*be*sta.cally*configured*– E.g.,*“map*12.34.158.0/24*to*Serial0/0.1”*• But,*this*doesn’t*adapt**– To*failures*– To*new*equipment*– To*the*need*to*balance*load*• That*is*where*rou.ng*protocols*come*in*11!Compu.ng*Paths*Between*Routers*• Routers*need*to*know*two*things*– Which*router*to*use*to*reach*a*des.na.on*prefix*– Which*outgoing*interface*to*use*to*reach*that*router*• Today’s*class:*just*how*routers*reach*each*other*– How*u*knows*how*to*forward*packets*toward*z012!12.34.158.0/24"Interface along !the path to z !u!z!Router z that can !reach destination!Compu.ng*the*Shortest*Paths*assuming*you*already*know*the*topology*13!Shortest‐Path*Rou.ng*• Path‐selec.on*model*– Des.na.on‐based*– Load‐insensi.ve*(e.g.,*sta.c*link*weights)*– Minimum*hop*count*or*sum*of*link*weights**14!3 2 2 1 1 4 1 4 5 3Shortest‐Path*Problem**• Given:*network*topology*with*link*costs*– c(x,y):*link*cost*from*node*x*to*node*y*– Infinity*if*x*and*y*are*not*direct*neighbors*• Compute:*least‐cost*paths*to*all*nodes*– From*a*given*source*u*to*all*other*nodes*– p(v):*predecessor*node*along*path*from*source*to*v*15!3 2 2 1 1 4 1 4 5 3 u!v!p(v)!Dijkstra’s*Shortest‐Path*Algorithm*• Itera.ve*algorithm*– Aier*k*itera.ons,*know*least‐cost*path*to*k*nodes*• S:*nodes*whose*least‐cost*path*defini.vely*known*– Ini.ally,*S*=*{u}*where*u*is*the*source*node*– Add*one*node*to*S*in*each*itera.on*• D(v):*current*cost*of*path*from*source*to*node*v*– Ini.ally,*D(v)*=*c(u,v)*for*all*nodes*v*adjacent*to*u*– …*and*D(v)*=*∞*for*all*other*nodes*v*– Con.nually*update*D(v)*as*shorter*paths*are*learned*16!Dijsktra’s*Algorithm*17!1 Initialization: 2 S = {u} 3 for all nodes v 4 if (v is adjacent to u) 5 D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Loop 9 find w not in S with the smallest D(w) 10 add w to S 11 update D(v) for all v adjacent to w and not in S: 12 D(v) = min{D(v), D(w) + c(w,v)} 13 until all nodes in SDijkstra’s*Algorithm*Example*18!3 2 2 1 1 4 1 4 5 3 3 2 2 1 1 4 1 4 5 3 3 2 2 1 1 4 1 4 5 3 3 2 2 1 1 4 1 4 5 3Dijkstra’s*Algorithm*Example*19!3 2 2 1 1 4 1 4 5 3 3 2 2 1 1 4 1 4 5 3 3 2 2 1 1 4 1 4 5 3 3 2 2 1 1 4 1 4 5 3Shortest‐Path*Tree*• Shortest‐path*tree*from*u* • Forwarding*table*at*u*20!3 2 2 1 1 4 1 4 5 3 u!v!w!x!y!z!s!t!v (u,v) w (u,w) x (u,w) y (u,v) z (u,v) link s (u,w) t (u,w)Learning*the*Topology*by*the*routers*talk*amongst*themselves*21!Link‐State*Rou.ng*• Each*router*keeps*track*of*its*incident*links*– Whether*the*link*is*up*or*down*– The*cost*on*the*link*• Each*router*broadcasts*the*link*state*– To*give*every*router*a*complete*view*of*the*graph*• Each*router*runs*Dijkstra’s*algorithm*– To*compute*the*shortest*paths*– …*and*construct*the*forwarding*table*• Example*protocols*– Open*Shortest*Path*First*(OSPF)*– Intermediate*System*–*Intermediate*System*(IS‐IS)*22!Detec.ng*Topology*Changes*• Beaconing*– Periodic*“hello”*messages*in*both*direc.ons*– Detect*a*failure*aier*a*few*missed*“hellos”*• Performance*trade‐offs*– Detec.on*speed*– Overhead*on*link*bandwidth*and*CPU*–
View Full Document
Unlocking...