Fichas
Routing
Fichas del conjunto (58)
- 1OverviewRIP, EIGRP, OSPF
Link State and Distance Vector Protocols - 2Network Layer Functions>transport packet sending to receiving hosts
>network layer protocols in every host, router
THREE IMPORTANT FUNCTIONS:
1) Path determination: route taken by packets from source to dest using routing algorithms
2) Switching: move packets from router's input to appropriate route output
3) Call setup: some network architectures require router call setup along path before data flows - 3Routing ConceptsLeast cost routing
>Number of hops
>Reliability, bandwidth, security
Non adaptive Routing (static)
>Selected pathway is the path for all packets
Adaptive Routing
>Router may select a new pathway for each packet - 4Virtual CircuitsSource-to-dest path behaves like telephone
-Call setup, teardown for each call before data can flow
-Each packet carries VC identifier
-Every router on source-dest path maintains state for each passing connection
-Link, router resources (bandwidth, buffers) may be allocated to VC to achieve circuit like performance - 5Virtual Circuit: Signalling protocol-Used to setup, maintain, and teardown VC
-Used in ATM, frame-relay, X.25
-Not used in today's internet - 6Datagram Network-No call setup network layer
-Routers: no state about end-to-end connections "stateless" no network-level concept of "connection"
-Packets typically routed using destination host ID
-Packets typically routed using destination host ID: packets between same source dest pair may take different paths - 7Routing-Routing protocols essential to operation of an internet
-Routers forward IP datagrams from one router to another on path from source to destination
-Routers must have idea of topology of internet - 8Fixed RoutingSingle permanent route configured for each source/dest pair
-Routes fixed
-May change when topology changes
-Link cost not based on dynamic data
-Based on estimated traffic volume or capacity of link - 9Static Routing IA router learns about network in two ways:
-Manually entered into the route table using static routes
-Static routes are not automatically updated - 10Static Routing IIUse when:
>Smaller networks that are not expected to grow
>Routing to and from stub networks
>SIngle default route to represent path to any network not found in the routing table - 11Static V DynamicDynamic:
-Generally independant of network size
-Auto adapts to topology changes
- - 12Floating Static Route>Used to provide a backup path
>Configured with higher admin distance (trustworthiness of path) - 13Routing Tables>One required for each router - there is an entry for each network (not dest). Routing only needs network portion.
>Each entry shows the next node on a particular route - 14Routing Tables (host)May also exist in hosts if multiple routers attached to a network, host needs table saying which to use. Other not necessary (if single router)
- 15Adaptive Routing IRoutes may change due to:
-Failure (routes change to route around problem area)
AND
-Congestion (routes change to route around clogged up areas) - 16Adaptive Routing IIDIS:
-More complex routing decisions involved thus more processing req.
-Depends on info collected in one place but used in another
-May react too slowly and become irrelevant
-May react too fast and cause congestion
>>>>>Can produce fluttering and/or looping - 17Fluttering I>Rapid oscillation in routing due to attempt to load balance or splitting
>Splitting traffic amongst routes may result in successive packets bound for same dest taking very diff routes - 18Fluttering IIISSUES:
If in one direction only, route characteristics may differ in two directions:
-TIMING and ERROR characteristics which may confused management and troubleshooting apps
Difficult to estimate RTT
TCP packets arrive out of order due to spurious retransmission and duplicate acks - 19Looping>Packet forwarded by router eventually returns to that router
>May occur when changes in connectivity not propagated fast enough to all routers - 20Classification of Adaptive Routing StategiesBased on INFO sources
LOCAL: route each datagram to network with shortest queue. May not be heading in correct direction but balance loads networks
ADJACENT NODES:
Distance vector algorithm
ALL NODES:
Link State algorithm - 21Routing ProtocolGoal is to determine a good path (sequence of routers) through which a datagram is forwarded from source to dest.
GOOD PATH = min cost path
These set up a routing table in routers - 22Routing Issue: Node makes local choices based on global topologiesCircumvent by having each router KNOW something about global state
Global state:= inherently large, dynamic and hard to collect - 23Requirements for routing tables>Minimise routing table space:= fast look up and less exchange
>Min num and freq of control messages
>Robustness:= avoiding black holes, oscillations and loops - 24Dynamic Routing Protocol ComponentsPurpose of dynamic routing protocols:
-Discovery of remote networks
-Maintaining up to date routing info
-Choosing best path to dest networks
-Ability to find new best path if current no longer available
MAIN components of these protocols:
-Data structures (tables/databases)
-Routing Protocols (to discover neighbouring routers aka RIP, exchange protocol info, maintain accurate info)
-Algorithms (for best path determination) - 25Dynamic Routing Classifications IGlobal (link state algorithm)
-all routers have complete topology, link cost info
Decentralised (distance vector algorithm)
-routers know physically connected neighbours link costs to neighbours
-iterative process of exchanging info with neighbours - 26Dynamic Routing Classifications IIStatic
Routes slowly change over time
Dynamic
routes change more periodically in response to link cost changes
Source-based:
packet header may contain entire route; if a link or router goes down the packet wont reach dest
Hop by hop:
packets only carry dest info, each router chooses next hop - 27Dynamic Routing Classifications IIISingle Path
router maintains single path to each dest
Multipath
router maintains primary and alternative paths - 28Two Fundamental Routing Algorithms for Packet Switch NetworksLink state and Distance Vector
Both know: a) address of each neighbour and b) cost of reaching each neighbour
AND both are distributed
Link state: A node tells every other node in the network its distance to its neighbours
Dist. Vector: A node tells its neighbours its distance to every other node on network - 29Distance Vector Routing IDist. Vector: A node tells its neighbours its distance to every other node on network
E.g. If A node was connected to D,F and E, it will broadcast knowledge about entire internetwork of D,F and E. - 30Distance Vector Routing II (Updating Algorithm)Router adds 1 hop to the hop count field for each advertised route
1.Add advertised dest if not in table
2.If dest in table
2a. Next hop field is same, replace the entry
2b. Next hop field is not same so:
-->i. Smaller hop count = replace entry
-->ii. Larger or equal hop count = do nothing - 31Distance Vector Routing IIIEach node exchanges info with neighbours directly connected by same network
Each node maintains three vectors: {link cost, distance vector, next hop vector}
Every 30 seconds exchange distance vector with neighbours - use this to update distance and next hop vector - 32Dynamic Routing Protocol Overview[Interior Gateway Protocols]
Distance Vector: RIPv2 and EIGRP (IPv4) + RIPng and EIGRP for IPv6 (IPv6)
Link State: OSPFv2 and IS-IS (IPv4) + OSPFv3 and IS-IS for IPv6 (IPv6)
Path Vector:
BGP-4
BGP-MP - 33Distributed Bellman Ford AlgorithmRIP is a distributed version of Bellman Ford
-Each simultaneous exchange of vectors between routers is equal to one iteration of step 2
At start up, get vectors from neighbours (gives initial routing). By own timer, update every 30 seconds. Changes are propagated across network. Routing converges within finite time (prop to num of routers) - 34RIP Routing Information ProtocolDynamic Routing protocol used to find the best path from source to dest by using distance vector routing
- 35RIP Updates-Updates do not arrive from neighbours within small time window
-RIP packets uses UDP
-Tables update after receipt of individual distance vector {1. Add any new dest network, 2. replace existing routes with small delay ones, 3. if update router T, update all routes using R as next hop} - 36RIP Topology Changes-If no updates received from a router within 180 seconds, mark route invalid -> assume router crash or network connection unstable (SET DIST VALUE TO 16 = infinity)
- 37RIP - Counting to INFINITY PROBLEMSlow convergence may cause: link cost == 1
SUPPOSE router D fails:
-B determine network 5 no longer reachable via D so set distance to 4 based on report from A or C
-At next update, B tells A and C this
-A and C receive this and increment their network 5 distance to 5 (4 from B + 1 to reach B)
-B receives distance count 5 and assumes network 5 is 6 hops away
-Repeat until infinity
-BASICALLY because link gone, and nodes rely on info from each other, then escalates out of control - 38RIP - Counting to INFINITY PROBLEM II (Split Horizon Solution)Counting Infinity Problem caused by misunderstanding between B and A, and B and C (Each thinks it can reach network 5 via the other).
SPLIT HORIZON dictates that you do not send info about a route back in the direction it came from -> erroneous route now eliminated in 180 secs - 39RIP - Poisoned ReverseSend updates with hop count 16 to neighbours for route learned from those neighbours
--->If two routers have routes pointing at each other advertising reverse route with metric 16, break loop immediately - 40RIP Packet FormatCommand : 1 = request, 2 = reply -> updates packets whether asked for or not. Initialising node broadcast request. Requests are replied to immediately
Version: 1 or 2
Address Family: 2 for IP
IP address: non-zero network portion, zero host portion (identifies particular network)
Metric: Path distance from this router to network - 41RIP LimitsDestination with metric more than 15 are unreachable - if larger metric allowed, convergence becomes lengthy
Simple metric leads to sub-optimal routing tables
Accept RIP requests from any devices (misconfigured devices can disrupt entire config) - 42Link State RoutingA router tells every other router in the network its distance to its neighbours
Router knows entire network topology (global info), and computes shortest path by itself
Key elements - topology dissemination, computing shortest routes - 43Link State: Topology DisseminationA router describes neighbours with a link state packet LSP which is used to control flooding to distribute this everywhere (store LSP in LSP database, and if new forward to every interface other than incoming one)
- 44Challenges for Link State RoutingEach LSP packet must have a seq. number --how do we know LSP is new,
-how many bits for SN
-how to detect router failure
-how to secure LSP database - 45Link State Algorithm: Dijkstra's Algorithm I-Computes least cost paths from one node (source) to all other nodes, and gives routing table for that node
-Link costs known to all nodes accomplished via 'link state broadcast'
Notation:
c(i,j): link cost from node i to j
D(v): cur val of cost of path from source to dest V
p(v): predecessor node along path from source to v
N: set of nodes whose least cost path is known - 46Link State Algorithm: Dijkstra's Algorithm II1.Initialisation
2.N={A}
3.for all nodes V
4.if v adjacent to A
5.then D(V) = c(A,v)
6.else D(v) = infinity
7. LOOP begin
7.1. find w not in N such that D(w) is a min
7.2 add w to N
7.3 update D(v) for all v adjacent to w and not in N
7.4 D(v) = min (D(v),D(w)+c(w,v))
7.5 *new cost to v is either old cost to v or known shortest path cost to w plust cost from w to v*
7.6 DO until all nodes in N - 47Hierarchical RoutingAggregates routers into regions:
(AS) Autonomous Systems: router in same AS run same routing protocol
Intra-AS routing: routers in different AS run different intra-AS routing protocol - 48Difference between intra routing and inter routingInter-AS is between different AS's
Intra-AS is within the same AS. - 49Autonomous SystemsGroup of routers exchanging info via common routing protocols
Set of routers managed by single organisation - 50IRP Interior Routing ProtocolPasses routing info between routers within AS
Does not need to be implemented outside AS
Need min info from other connected AS (at least one router in each AS must talk to the other AS) - 51Exterior Routing AlgorithmRouter in first system determines route to target AS. Routers in target AS then coop to deliver datagram
Passes less info than IRP - 52Interior vs Exterior
- 53Routing in the INTERNETGlobal Internet consists of AS Autonomous Systems interconnected with each other:
-Stub AS: small corp
-Multihomed AS: large corp
Transit AS: provider
Two Level Routing:
Intra-AS: admin responsible for choice
Inter-AS: unique standard - 54Intra-AS RoutingKnown as Interior Gateway Protocols (IGP)
Common ones include:
-RIP: Routing Info Protocol
-OSPF: Open Shortest Path First
EIGRP: Interior Gateway Routing Protocol - 55OSPF Open Shortest Path FirstOpen as in publicly available
Uses LINK STATE ALGORITHM (routing computation via dijkstra)
OSPF advert carries one entry per neighbour router
Advertisements disseminated to entire AS - 56OSPF specific FEATURES (not in RIP)Security - all OSPF messages are authenticated to prevent malicious intrusion
Multiple same cost paths are allowed (only one in RIP)
For each link, multiple cost metrics for diff TOS
Integrated uni and multicast support (multicast OSPF uses same topology as OSPF)
Hierarchical OSPA in larger domains - 57Hierarchical OSPFTwo level:
local area and backbone
-Link state adverts only in area
-Each node has detailed area topology; only know shortest path to nets in other areas
>Area border routers summarise distances to nets in own area, advertise to other Area Border routers
>Backbone routers: run OSPF routing limited to backbone
>Boundary routers: connect to other AS's - 58OSPF OverviewRouter maintains descriptions of state of local links
Transmits updated state into to all routers that it knows about
Router receiving update must ack that lots of traffic generated
Each router maintains database
Información
- Descripción
- Fichas sobre Routing, creado por Eric Wojcik el 12/06/2018.
- Creado por
- Eric Wojcik
- Visitas
- 0
- Valoración