1、10/9/2018,ECE697F: Special Topics-Internet Routing,1,Introduction to Internet Routing,Lixin Gao ECE Dept. UMASS, Amherst,ECE697F: Special Topics-Internet Routing,2,Routing Protocols,Goal: Determine path or route Packet switching networks: determine routing table Routing Table: Used for forwarding ea
2、ch packet Scalable, adaptive, stable,ECE697F: Special Topics-Internet Routing,3,Internet Protocol Stack,Application Transport Network Link Physical,ECE697F: Special Topics-Internet Routing,4,Route Construction,Static Listed Manually: change route slowly not robust: reachability is independent of net
3、work condition stableDynamic Learn route via routing protocols React to topology, traffic or configuration changes directly Might not converge or oscillate Might have loop,ECE697F: Special Topics-Internet Routing,5,Dynamic Routing Algorithms,Global or Link state algorithm Use global knowledge about
4、topology and costDecentralized or Distance Vector algorithm Use only knowledge of attached links and neighbors Distributed and iterative algorithm,ECE697F: Special Topics-Internet Routing,6,Global or Link State Algorithm,Dijkstras shortest path algorithm Implementation: Each node broadcast its conne
5、ctivity and link costs to all nodes,ECE697F: Special Topics-Internet Routing,7,Link State Algorithm Issues,Scalability Link cost is traffic carried: can cause route oscillation,1,1+e,e,0,e,1,1,0,0,0,2+e,1+e,1,0,0,recompute, recompute,recompute,initially,ECE697F: Special Topics-Internet Routing,8,Dec
6、entralized or Distance Vector Algorithm,each node communicates only with directly-attached neighbors compute shortest path continues until no nodes exchange information nodes need not exchange info/iterate in lock step!,ECE697F: Special Topics-Internet Routing,9,Distance Vector Algorithm Issues,Robu
7、stness: node can advertise incorrect path cost each nodes table used by others error propagate thru network may have routing loops Convergence Times: count-to-infinity problem,ECE697F: Special Topics-Internet Routing,10,Evolution of the Internet,NSFNET Backbone,Regional Backbone,Regional Backbone,Re
8、gional Backbone,Regional Backbone,Campus Network,1986-1995,ECE697F: Special Topics-Internet Routing,11,Internet Today,NSFNET decommissioned in 1995: commercialization of the Internet,(Inter)National Provider,(Inter)National Provider,Regional Provider,NAP,Private Peering,ECE697F: Special Topics-Inter
9、net Routing,12,Network Access Point (NAP),MAE-East MAE-West Sprint NAP,FDDI Ring,AT&T,MCI,vBNS,ECE697F: Special Topics-Internet Routing,13,Private Peering,AT&T,MCI,Exchange Traffic,ECE697F: Special Topics-Internet Routing,14,Internet Architecture,Segregated to Autonomous Systems (ASes) belong to ISP
10、s Companies Universities One ISP might own several ASes ISP Merger,ECE697F: Special Topics-Internet Routing,15,Inter-AS and Intra-AS Routing,AS1,AS2,Inter-AS routing,Intra-AS routing,ECE697F: Special Topics-Internet Routing,16,Why different Inter-AS and Intra-AS routing protocols?,Administrative: ea
11、ch AS runs different intra-AS routing protocol Policy: AS has commercial agreement that determines routing policy Scalability or hierarchy: hiding information within AS reduce the routing message size.,ECE697F: Special Topics-Internet Routing,17,Forwarding Table,Inter-AS Routing,Intra-AS Routing,Rou
12、ting Table,ECE697F: Special Topics-Internet Routing,18,Inter-AS Routing Protocols,Use EGP in NSFNETBorder Gateway Protocol (BGP) BGP-4: de facto standard Distance Vector Algorithm,ECE697F: Special Topics-Internet Routing,19,Intra-AS Routing,Routing Information Protocol (RIP) Distance Vector Algorith
13、m Open Shortest Path First (OSPF) Link State Algorithm IS-IS Link State Algorithm,ECE697F: Special Topics-Internet Routing,20,Border Gateway Protocol (BGP),MCI,AT&T,BBN,d,Exchange reachability informationApply local policies for announcing and selecting routeAvoid Route Loops Incremental UpdateUse T
14、CP,AS7018,AS701,AS1,(1), (7018,1),(1), (701, 1),ECE697F: Special Topics-Internet Routing,21,OSPF,Hierarchy: Divided into Areas Load balancing: Multiple same-cost paths Security: Authenticate update messeges,ECE697F: Special Topics-Internet Routing,22,Where do link costs and routing policies come fro
15、m?,Someones head Manually entered Router Configuration Cause failure,ECE697F: Special Topics-Internet Routing,23,Routing Protocol Issues,Stability Policy Effect Congestion Effect Protocol Design Effect Keep Alive Message Redundant Incremental Update message ? Reliability or Robustness Alternate or Backup route Congestion Effect Human Error,ECE697F: Special Topics-Internet Routing,24,More Issues,Convergence Speed Security Scalability Hierarchy Traffic Engineering Load Balancing Qos ?,
