Transcript Node 1 `s Topology Table

ITEC4610
Network Switching and Routing
ดร. ประวิทย์ ชุมชู
หัวหน้าสาขาวิชาวิศวกรรมสารสนเทศและการสื่ อสาร(ICE)
MUT
Email: [email protected]
ห้องทางาน: F402
เบอร์โทรศัพท์ที่ทางาน: (02)9883655 ต่อ 220
เบอร์โทรศัพท์เคลื่อนที่: 065343850
MUT
Class VI
EIGRP (Enhanced Internal Gateway Routing Protocol)
ดร. ประวิทย์ ชุมชู
หัวหน้าสาขาวิชาวิศวกรรมสารสนเทศและการสื่ อสาร(ICE)
MUT
Email: [email protected]
ห้องทางาน: F402
เบอร์โทรศัพท์ที่ทางาน: (02)9883655 ต่อ 220
เบอร์โทรศัพท์เคลื่อนที่: 065343850
MUT
Objectives
• การทางานของ DUAL
• การทางาน EIGRP
•
•
•
•
•
MUT
Neighbor discovery and Recovery
Reliable Transport Protocol (RTP)
Dual-finite State machine
PDM (Protocol-dependent Module)
ประเภทของข้อมูลที่ใช้ในการสื่ อสารระหว่างเร้าเตอร์
Routing Algorithms
• Distance vector routing ถูกใช้ใน RIPv1 RIPv2 IGRP
• Link-state Routing ถูกใช้ใน OSPF
• Advanced distance-vector ถูกใช้ใน EIGRP
– Dual (Diffusing Update Algorithm)
MUT
Distance vector routing
• Initialization
– เริ่ มต้นสร้าง routing table
• Sharing
– การแลกเปลี่ยน routing table
• Updating
– การแก้ไข routing table
• คานวณเส้นทางโดยใช้
– Bellman-ford’s algorithm
MUT
Link-State routing
•
•
•
•
เริ่ มต้นตรวจสอบสถานะของลิงค์
แต่ละโหนดเก็บ link states ของตัวเอง
กระจาย link states ให้โหนดอื่นภายในพื่นที่ (flooding)
คานวน shortest path ของจากโหนดตัวเองไปยังโหนดอื่น ๆ โดยใช้
– Dijktsta ‘a algorithm
MUT
เปรี ยบเทียบ Distance-vector และ Link state
• ข้อดี
– ใช้หน่วยความจาน้อย
– การคานวณไม่ซบั ซ้อน
• ข้อเสี ย
– Slow convergence
– สามารถเกิด routing loop
MUT
• ข้อดี
– Fast convergence
• ข้อเสี ย
– ใช้หน่วยความจามาก
– การคานวณซับซ้อนกว่า
ตัวอย่างการทางานของ RIP
Node 2
Node 3
Node 1
Link 1-5
Node 5
Node 4
Network A
Node 2 ’s routing Table
Dst
A
...
MUT
Next-hop
Node 1
...
Cost
2
...
ถ้า link 1-5 มีปัญหา
Node 2
Node 3
Node 1
Link 1-5
Node 5
Node 4
Network A
• Node 2 ไม่สามารถส่ งข้อมูลไปยัง Network A
• รอจนเกิด timeout (90 second)
• ใช้เวลาประมาณ 90-120 วินาทีในการที่จะได้เส้นทางใหม่ไปยัง
ไปยัง network A โดยผ่านเร้าเตอร์ 3
MUT
Dual
•
•
•
•
•
•
MUT
Advance Distance Vector
Compute shortest path distributedly
No Routing Loop
No Counting-to-Infinity behavior
Performance better than DV
Performance similar to the performance of LS
ตัวอย่างการทางานของ DUAL
Node 2
Node 3
Node 1
Link 1-5
Node 5
Node 4
Network A
Node 1 ’s Topology Table
MUT
Network
Via
Feasible Advertised Added to topology/routing
Distance distance
table?
A
A
…
Node 1
Node 2
…
2
3
…
1
2
…
yes /yes
yes /no
..
ถ้า link 1-5 มีปัญหา
• Node 2 ไม่สามารถส่ งข้อมูลไปยัง Network A
• เปลี่ยนเส้นใหม่ไปยัง network A โดยผ่านเร้าเตอร์ 3
MUT
EIGRP
•
•
•
•
•
•
•
•
•
•
Improved version of IGRP
Backwards compatible with IGRP
Improved convergence
Sends updates like a link state routing protocol
Supports VLSM/CIDR
Supports many layer 3 routed protocols (not just IP)
Routing protocol designed by Cisco
Combines best features of link-state and distance vector routing protocols
Compatible with IGRP
Two major versions
– Version 0
– Version 1
MUT
Advantages of EIGRP
•
•
•
•
•
MUT
Rapid convergence
Low routing update traffic
Support for multiple protocols
Support for VLSMs and classless routing
Support for route summarization along arbitrary boundaries
EIGRP Features
Network A
•
•
•
•
Hellos sent every 5 secs
Neighbour table
Topology table
DUAL takes information in
neighbour & topology table and
calculates best routes (‘successors’)
and adds them to the Routing Table
• ‘Feasible successors’ are alternative,
backup routes
A
(1)
(1)
D
B
(2)
(1)
(2)
(1)
C
Number in () = metric
MUT
E
Hybrid Routing Protocol Features
• Hybrid of link-state and distance vector routing protocols
• Learns routes from connected interfaces or their neighbors
• Does not need to know entire network topology
– Does not require much memory or CPU to calculate routing tables
• Saves bandwidth by sending routing updates only to routers that need
the information
MUT
EIGRP Strategies to Avoid Routing Loops
• Uses Diffusing Update Algorithm (DUAL)
– Routers store back-up routes by using topology table
– Topology table contains only routes advertised by neighboring routers
– Comparison of EIGRP with RIP and OSPF
• RIP is pure distance vector routing protocol
• OSPF is pure link-state routing protocol
• การพิสูจน์วา่ ไม่มี Loop สามารถอ่านเพิ่มเติม
– J.J.Garcia-Luna-Aceves, “Loop-Free Routing Using Diffusing
computations,” IEE/ACM networking, Vol. 1, No. 1, February 1993.
MUT
EIGRP Operation
• Uses hello packets to identify neighbors
• Uses reliable transport to exchange routing information
• Stores information about neighbors and their routes
– Uses this information to build routing tables
MUT
EIGRP Technologies
• Hellos multicast every 5 seconds to 224.0.0.10
• Holdtime (route dead) - 3 x hello interval
• RTP used as a reliable transport protocol to remain protocol
independent
• Sequence numbers used on replies/acknowledgements to hellos –
unicast NOT multicast
• Multicast update packets sent when topology changes
MUT
Transmission of EIGRP Packets
• On IP network, EIGRP uses IP packets
– Identified as protocol 88 in the IP header
• Reliable Transport Protocol (RTP) has sequence number in each packet
– Requires explicit acknowledgement for each packet sent reliably
– RTP builds transmission list for each neighbor and retransmits up to 16 times
or until hold time expires
MUT
Multicast Packets with EIGRP
• Multicast packet to all neighbors is more efficient than multiple hello
packets requiring acknowledgement
• RTP flag in packet indicates no acknowledgement is necessary
• RTP flag also used in packets carrying routing updates
MUT
Five Types of EIGRP Packets
•
•
•
•
•
MUT
Hello packets
Update packets
ACK packets
Query packets
Reply packets
EIGRP packets
• The destination IP address in EIGRP depends on the packet type--some
packets are sent as multicast (with an address of 224.0.0.10) and others
are sent as unicast
• The source IP address is the IP address of the interface from which the
packet is issued.
• Following the IP header is an EIGRP header.
MUT
An EIGRP header
The fields following the EIGRP
header depend on the opcode field.
MUT
IP internal route updates
-Type field of 0x0102
-The next hop identifies the router to send packets destined for destination
-The prefix length field signifies the subnet mask
MUT
IP external route updates
MUT
Building and Maintaining Neighbor Relationships
• Hello packets discover and maintain relationships with neighboring
routers
• Packets sent at hello interval
– Default is 5 seconds for fast interfaces and up to 60 seconds for slower links
– Default hold time is three times the hello interval but may be up to 180
seconds for slower links
– Hello interval and hold time may be configured independently
MUT
Exchanging Neighbor Information in Hello Packets
• To become neighbors, routers must share
– Common subnet
– Same Autonomous System number
– Same constants to calculate EIGRP’s metric
MUT
Neighbor Table
• Neighbor table contains information about router’s neighbors
including:
–
–
–
–
–
–
–
MUT
Neighbor address and interface
Hold time and Uptime
Smooth round trip timer (SRTT)
Retransmission timeout (RTO)
Handle (H)
Queue count
Sequence number
Building the Topology Table with Update Packets
• Topology table consists of all the routes each neighbor advertises
– Includes metrics advertised by neighbors for routes
– Includes metric the router itself uses to forward packets to those destinations
• Adds metric to get to neighbor to metric advertised by neighbor to destinations
MUT
Building and Maintaining Routing Tables
• Building routing tables for first time
– When router becomes part of EIGRP network, it sends out hello packets on
all interfaces
– Neighbor replies with update packets containing Init bit to indicate a new
neighbor relationship.
– New router acknowledges each update packet and uses information in
packets to builds its topology table
– New router then sends update packets to all neighbors
– Each neighbor replies with an ACK
– See the Table in the next slide
MUT
Building a Routing Table for the First Time
MUT
Building Routing Tables
• Uses DUAL algorithm to select primary and back-up routes for each
destination
– Includes these routes in its topology table
• Supports internal, external, and summary routes
• Adds best route into routing table as successor route
MUT
ตัวอย่างการคานวณด้วย DUAL
Network A
A
(1)
(1)
D
B
(2)
(1)
(2)
(1)
C
Number in () = metric
MUT
E
EIGRP Metric
• Five variables used to calculate metric
–
–
–
–
–
Bandwidth
Delay
Reliability
Load
Maximum transmission units (MTU)
• Uses constants, called K-values, to calculate final metric
• Final metric value multiplied by 256 results in a 32-bit metric value
MUT
Default K-values
bandwidth (kbps)
MUT
Delay (tens of microsecond)
ตัวอย่างการคานวณ Metric
Node 4
B=56
d=2000
Node 2
B=128
d=1000
Network A
Node 1
Node 3
B=10000
d=100
B=10000
d=100
B= bandwidth (kbps)
d= Delay (tens of microsecond)
MUT
ตัวอย่างการคานวณ metric
•
•
•
•
•
Metric=[K1*bandwidth+(K2*bandwidth)/(256-load)+K3*delay)]*[K5/(Reliability+K4)]
K1=1, K2=0, K3=1, K4=0, K5=0
Metric =[bandwidth + delay]
No floating point, Round down
Router 1 to Network A
– Via router 4
• (10,000,000/56+2200)*256=(180771+2200)*256=46277376
– Via router 3
• (10,000,000/128+1200)*256=(78125+1200)*256=79325*256=20307200
• Router 1 to Network A: Via router 3
MUT
Maintaining Routing Tables with the DUAL Algorithm
• DUAL is a finite state machine
– Each state is loop-free routing table
– DUAL watches for topology changes
• Selecting best path with DUAL Algorithm
–
–
–
–
MUT
Advertised distance (AD) or lowest cost is advertised to neighbors
Feasible distance (DF) is total metric to destination
Successor or lower cost loop-free path is added to routing table
Current successor is primary route to any destination
Route States (two states)
•
•
•
•
•
•
Active - recomputation is being performed
Passive - no recomputation going on
If feasible successors are always available, a destination never goes into the active state.
Recomputation occurs when no feasible successor route exists
If a neighbor who is the only feasible successor to a destination goes down, all of the neighbor's routes enter the
active state and trigger route recomputation.
Recomputation Process
– Send a query packet to all neighboring routers
– Neighbor sends
• a reply that it has a feasible successor, or
• a query packet to indicate it is partcipating in the recomputation
– Routes in the active state cannot have their routing table information changed
– Once all neighbors have replied the topology table entry for the destination returns to the pasive state and the router may
then select a feasible successor.
MUT
Selecting Feasible Successors
• Feasible successor is next best route to destination
• EIGRP may keep more than one feasible successor in its topology table
• Next hop router must have advertised distance to destination less than
feasible distance of route of current successor
• Helps prevent routing loops
MUT
Failure of the Primary Route
• DUAL algorithm looks at each feasible successor in topology database
– Chooses one with lowest metric; does not have to recalculate it
• If no feasible successor exists, router queries neighbors in query range
with split horizon rule to find new route
– New route goes from passive to active state and must be recalculated
• If no response to query packet within time limit, router enters stuck-inactive (SIA) state
MUT
Topology Change on an EIGRP Network
• When router joins network, it builds routing table, using information
from neighbors.
• If more than one possible path exists to a network, router chooses path
with best feasible distances
• If serial link goes down, router must find a new route to destination
network
MUT
Example Network
MUT
Router A’s Possible Topology Table Entries
MUT
Network with Serial Interface Down
MUT
Using EIGRP on Very Large Networks
• Use special care to minimize routing problems and convergence time
• EIGRP scalability is affected by variables
–
–
–
–
MUT
Number of routers involved in network change
Amount of routing information exchanged by EIGRP neighbors
Number of hops information travels to reach all affected routers
Number of redundant paths on network
Restrict and Eliminate Queries
• Lost reply packets result in serious convergence problems
• Heavy CPU or memory usage on router causes problems
• The larger the query scope in an Autonomous System, the more likely
routers are to end up in SIA mode
– Size of query depends on number of neighbors and number of paths a query
might take
MUT
Restricting Query Scope
• Segment a network into multiple Autonomous Systems
– May not solve problem
• Use route summarization
– May not solve problem
• Summary routes must be placed appropriately
MUT
Restricting Queries with Multiple EIGRP Autonomous Systems
MUT
Route Tagging
• Internal routes come from neighbors with the same (E)IGRP AS number or from
directly attached interfaces over which IGRP or EIGRP runs.
• External routes come from other routing protocols or from static routes and are
tagged with the following information:
–
–
–
–
–
–
MUT
Router ID of the router that distributed the route
AS number of the destination
Configurable administrator tag
ID of the external protocol
Metric from the external protocol
Bit flags for default routing
เปรี ยบเทียบ
MUT
Disadvantages of EIGRP
• Proprietary to CISCO
• Routers from other vendors cannot use or understand EIGRP
MUT
ตัวอย่าง
Node 2
Node 3
Network D
Network E
Node 1
(3)
(2)
(2)
Network C
(1)
Node 5
Network F
(4)
(5)
Network B
Node 4
Network A
ลองสร้ าง Topology Table ของ router 1 ดู
ลองสร้ าง Routing Table ของ router 1 ดู
MUT
Node 1 ’s Topology Table
MUT
Network
Via
Feasible Advertised Added to topology/routing
Distance distance
table?
A
A
…
Node 1
Node 2
…
2
3
…
1
2
…
yes /yes
yes /no
..
ตัวอย่าง
Node 2
Node 3
Network D
Network E
Node 1
(3)
(2)
(2)
Network C
(1)
Node 5
Network F
(4)
(5)
Network B
Node 4
Network A
MUT
LS routing
ลองสร้ าง Topology Table ของ router 1 ดู
ลองสร้ าง Routing Table ของ router 1 ดู
ตัวอย่าง
Node 2
Node 3
Network D
Network E
Node 1
(3)
(2)
(2)
Network C
(1)
Node 5
Network F
(4)
(5)
Network B
Node 4
Network A
MUT
DV routing
ลองสร้ าง Topology Table ของ router 1 ดู
ลองสร้ าง Routing Table ของ router 1 ดู