DVMRPandMOSPF

Information about DVMRPandMOSPF

Published on January 1, 2008

Author: Alien

Source: authorstream.com

Content

Multicast Routing Papers: DVMRP and MOSPF:  Multicast Routing Papers: DVMRP and MOSPF Bridges and Extended LANs:  LANs have physical limitations (e.g., 2500m) Connect two or more LANs with a bridge transparent to hosts (does not add packet header) Bridge sees all messages in its attached LANs Copy message from one LAN to another if necessary Bridges and Extended LANs A Bridge B C X Y Z Port 1 Port 2 Port 3 H I J Learning Bridges :  Forward messages only when necessary (without modifying the message in any way). Maintain a forwarding table Often incomplete (initially empty!) Learn table entries based on source address of messages seen. If destination is not on table, forward over all other ports Learning Bridges A Bridge B C X Y Z Port 1 Port 2 Port 3 H I J Host Port A 1 B 1 C 1 X 2 Y 2 H 3 Learning Bridges :  I sends a message to Z Bridge “learns” I comes from port 3 I is added to the table Z is unknown bridge copies the message over BOTH port 1 and port 2 Learning Bridges A Bridge B C X Y Z Port 1 Port 2 H I J Host Port A 1 B 1 C 1 X 2 Y 2 H 3 Port 3 Z sends a message to I (e.g. some reply) Bridge “learns” Z comes from port 2 Z is added to the table bridge copies the message ONLY over port 3 (I is already in the table) Spanning Tree Algorithm :  Spanning Tree Algorithm Problem: loops Bridges run a distributed spanning tree algorithm Logically delete certain bridges to have a spanning tree We will assume we have a spanning tree B3 A C E D B2 B5 B B7 K F H B4 J B1 B6 G I B3 A C E D B5 B B7 K F H B4 J B1 G I Multicast Routing in Datagram Internetworks and Extended LANs:  Multicast Routing in Datagram Internetworks and Extended LANs S. Deering and D. Cheriton ACM Transactions on Computer Systems 1990 Efficient multicast in Extended LANs:  Efficient multicast in Extended LANs How to do efficient multicast in Extended LANs? (I.e. in LANs with bridges) Bridges propagate broadcast (and multicast) packets across every segment of the extended LAN Way too inefficient, especially for multicast applications with sparsely located receivers Find an efficient way of doing multicast and convert applications to use multicast How to do multicast better in Extended LANs? Single Spanning-Tree Multicast Routing:  Single Spanning-Tree Multicast Routing If bridges know which interface led to members of a given group, they will forward the packets on those interfaces only But, in general, how do bridges learn which interface leads to individual hosts? When a packet arrives from a host, bridge records the (source-host addr, interface, age) into a table If an entry is too old, it is removed (self-cleaning table) We want to forward multicast packets only over LANs leading to receivers Problem: a bridge does not learn about a receiver host (i.e. a group member) unless the bridge receives a packet from the host (receivers don’t send data !!!) Instead, group members (receivers) periodically transmit a membership-report Multicast Table:  Multicast Table Arrow indicates where group members are located Multicast table of each bridge has the following row for each multicast group: (muticast addr, (outgoing interface, age), (outgoing interface, age), … ) A member of a group G sends a membership-report, source address = G, destination address = “ALL-BRIDGES” multicast address. Bridge receiving this message records this interface as an outgoing interface for group G It then forwards this report to other bridges (out all of its interfaces) in the extended LAN (why over all interfaces? I.e., why a broadcast?) Single Spanning-Tree Multicast Routing:  Single Spanning-Tree Multicast Routing Bridge algorithm (summary) If source address is a mcast group address (i.e. a report), record arriving interface as an outgoing-interface with an age of zero into the table entry for this mcast address and forward to all other interfaces. Periodically increment age of outgoing interface when age=expiry threshold, delete this outgoing-interface info from the table’s entry if no outgoing-interfaces remain, delete the entire entry If a packet arrives with multicast dest addr forward a copy on every outgoing-interface recorded in the table entry (if any) excluding the arriving interface Another example:  Another example B3 A C E D B5 B B7 K F H B4 J B1 G I G G = group G member (receiver) G Arrows indicate the location of the group member Membership reports are forwarded over all links of a bridge What if a host at E sends a msg to group G? Suppressing Membership Reports:  Suppressing Membership Reports An efficiency improvement to suppress unnecessary membership reports Hosts send membership-reports as (G,G) This suppresses #membership reports to 1 per report interval because all other group members (hosts) on the same LAN heard the first membership-report (G,G), and will not send a report Bridge, on receiving a pkt with address (G,G) (bridges receive ALL packets, remember?) changes it to (G, all-bridges) and forwards to other interfaces Why change the destination? :  Why change the destination? Why does the router change from (G,G) to (G, “ALL-BRIDGES”)? G1 bridge G2 Assume member G1 sends a membership report (G,G) over lan A Assume the bridge forwards it as (G,G) over lan B This will suppress the membership report of G2 The bridge will never know there is a group member in lan B A B Slide14:  Done with extended LANS (bridges) Now we do multicast over multiple LANs (across routers) Distance Vector Multicast Routing:  Distance Vector Multicast Routing How to support multicast routing in a distance-vector environment? (this is general enough for ANY unicast routing protocol) Compute a spanning (i.e. broadcast) tree across all the links and prune it to become a multicast tree Specifically, a source-based shortest path spanning trees Tree is rooted at the source site It corresponds to shortest path from each receiver to the source Main assumption is path symmetry (links have the same costs in both directions) Observation: Every shortest-path multicast tree rooted at the sender is a subtree of a single shortest-path spanning (i.e. broadcast) tree rooted at this sender Broadcast Trees and Multicast Trees in Point-to-Point Networks:  S S S R R Network Multicast Tree Broadcast Tree V U S = source (host) node, also root of tree R = receiver For any router U, parent(U) = next-hop(U,S) = V Broadcast Trees and Multicast Trees in Point-to-Point Networks R R Reverse Path Flooding (RPF) algorithm (broadcast in point-to-point networks):  Reverse Path Flooding (RPF) algorithm (broadcast in point-to-point networks) This is not a standard protocol, is just a general method to do broadcast. When a router receives a broadcast packet from source S If the packet arrives via the shortest path from the router back to S Then, Forward the packet all outgoing interfaces (except the incoming one, of course) Otherwise Throw the packet away Note: each router forwards each packet only once (why) Router needs to know the shortest path back to S Given by the distance vector routing algorithm Example:  Example S v u t Which of all three copies will be forwarded by t? Internetworks:  Internetworks Original RPF is designed considering point-to-point links In the Internet we typically have LANs (e.g. Ethernet) There are many routers per LAN A multicast packet sent by a source host S will have LAN source: LAN address of S LAN destination: LAN multicast address for group G IP source: IP address of S IP destination: IP multicast address for group G Routers do not modify the IP src or dst addresses Routers send the packet over the LAN with LAN source: LAN address of router LAN destination: LAN multicast address for group G All routers “listen” (receive a copy) of all LAN packets addressed to any multicast group. A problem with original RPF :  A problem with original RPF When shared links (Ethernet) used between routers, two problems Multiple copies of the packet is sent on the shared link: Multiple routers are attached to the same LAN (Ethernet) Waste of bandwidth on the link & waste of router resources We want only one copy to be sent per LAN Identifying the parent on the tree: In RPF, routers only accept a broadcast packet from the next router on the path back to S. How does this router learn which packet is coming from its parent? We will eliminate this requirement since only one packet is sent per LAN. A packet is accepted if it comes from the LAN of its next-hop. Reverse Path Broadcasting (RPB):  Reverse Path Broadcasting (RPB) Eliminates duplicate broadcasts on shared links in RPF Identify a single “parent” router for each link w.r.t. S For the link S is attached to, S is considered the parent Otherwise, router with min distance to S is the parent In case of tie, router w/ lowest IP address is the parent Slide22:  RPF: Both x and y inject packets into a z only forwards the copy it receives from x, because x is its next hop to S RPB: x, y and z learn that only x should inject packets into a z forwards any multicast from S coming from a (even if it arrives from y) Slide23:  S Y X Z L Path of broadcast messages Observations:  Observations How to identify min distance router to S? Routers exchange distance vector records with each other Therefore, each router independently finds its parent If multiple routers with same distance the way ties are broken by unicast routing does not matter what matters is the LAN of the chosen next hop Overhead: Parent selection requires that routers add a children bitmap to each routing table entry (i.e. each destination LAN could be a possible source LAN S) the bit-map for “destination” S has one bit for each incident link l Bit (S,l) is set, if l is a child link (i.e. if I am the parent of this link) for broadcasts originating from S Example:  Example Routing table at U Dest NxtHop Cost ChildMap ------------------------- A X 5 01110 B Y 2 01000 . . . S V 2 01011 U V S 0 1 1 0 1 Pruning the Tree:  Pruning the Tree Both RPF and RPB are broadcast algorithms ! To provide shortest path multicast delivery from source S to group members, broadcast tree of S must be pruned back to reach only links with receivers May be accomplished by requiring members of G to send membership reports back up the broadcast tree of S periodically Each tree is identified by the pair (S,G) Too costly – membership reports have to be done for each pair (S,G), not just for every G. What if only a few sources are active at a time? We want to do this only for active sources Truncated Reverse-Path Broadcast (TRPB):  Truncated Reverse-Path Broadcast (TRPB) An alternative in which only non-member leaf LANs are deleted from each broadcast tree Truncate child link if no router uses this link to receive multicast messages from the source (i.e., it is a leaf link) No host is a group member on this link (LAN) Leaf Truncation example:  Leaf Truncation example At L, L truncates the lower LAN in the figure if if Z does not accept multicast messages from this LAN No host is a group member on this link (LAN) Y X Z L Path of broadcast messages Slide29:  S Y X Z Receiver Receiver L X cannot cut this child LAN since Z uses this LAN as its next hop (not leaf link) L truncates this LAN since Z does not use L to reach S (it is a leaf link) and there are no receivers. Algorithm:  Algorithm If a multicast packet (S, G) arrives from the next-hop-link for S, forward a copy of the packet on all child links for S, except leaf links (no other router receives from this link) that have no members of G To implement this, we need two things: The router needs to learn if the child link is a leaf link I.e. If no other router uses this link to receive messages from the group. The router also needs to know if no host group members are on this link. Implementation:  Implementation Leaf pruning requires that routers add a leaf bitmap to each routing table entry (i.e. for each possible source) the bit-map for routing table entry S has one bit for each incident link l bit for (S,l) is set, if l is a leaf link of this router for multicasts originating from S How to know if the link is a leaf link? Implementation (continued…) :  Implementation (continued…) Distance vectors tell me the distance from routers on this link to S, but not if I am their next hop. However, if DV with split-horizon and poisoned-reverse is used then If a router gives me a distance of infinity then it uses my LAN as the next hop I.e., the link is not a leaf link Implementation (contd)…:  Implementation (contd)… (Paper  ) Hosts send a membership report message over their LAN using the mcast group address as the destination (all hosts group members listen to this, and only one report is sent per interval) Real Life: use IGMP protocol. Routers maintains a table with one entry per link (LAN) The entry contains a bit-map field, link-groups, with one bit per (active-group,link) Bit (l,G) is set if members of group G are on link l Overview of “bitmaps” required:  Overview of “bitmaps” required For each source S and each link l, Is l a child link of the router on the broadcast tree of S? Is l a leaf link of the router on the broadcast tree of S? Both of these are obtained via the DV routing algorithm (the second one via split horizon with poisoned reverse) For each link l and active group G, Does l have any members of G? Obtained via membership reports (IGMP) Reverse Path Multicasting (RPM):  Reverse Path Multicasting (RPM) Prune shortest path multicast tree as follows First packet for (S,G) is forwarded to everyone on the truncated shortest path broadcast tree according to TRPB Leaf routers (i.e., all child links are leafs) with no attached members send nonmembership report (NMR) to their parent on the tree If a router receives NMR from all of its children routers and itself has no directly attached members, it also sends NMR to its parent router on the tree. Slide36:  S H Y X Z R R NMR NMR L NMR NMR NMR Slide37:  S M Y X Z R R L Cannot be truncated because there is a receiver here. NMR expiration:  NMR expiration NMR reports include an age field, when it expires data flows all the way to leaves again and gets re-pruned back Routers remember NMR reports that they sent When a new host joins G, they send a cancellation message to undo the effect of NMR Pros and Cons :  Pros and Cons Reverse path multicasting, when used with distance vector routing, is known as distance-vector multicast routing protocol (DVMRP) Advantages: good when there are many receivers, since multicast messages are initially flooded to the entire network. Disadvantages Bad if there are few receivers Again, the first multicast messages are sent throughout the network unnecessarily. Routers need to remember the “prune” state, i.e. they need to maintain state even when there are no receivers below them on the tree The path from source to receiver may not be optimal if the cost of links is not bi-directional. Link-State Multicast Routing:  Link-State Multicast Routing This is covered in the book, section 4.4.1 Extend OSPF – MOSPF Send group membership information in OSPF link state advertisement (LSA) messages I.e., each router learns the entire set of receivers, and their location. Each router can compute the minimum cost path from every source to the current set of receivers of the multicast group. Slide41:  A B C R(G) R(G) S(G) Routers A and B mention in their LSA that they have receivers in their adjacent LANs. Hence, C can recreate the above picture in detail. Slide42:  A B C R(G) R(G) S(G) C computes the shortest path tree from S(G) to the receivers Each link is tagged with its distance to the closest R(G) 2   How do you know who are the sources?:  How do you know who are the sources? You could precompute, for every group G, a tree for every source S This is way too expensive Instead, use caching MOSPF Cache:  MOSPF Cache The cache has entries of the following form: (S, G, iif, min-hops) Min-hops is a VECTOR with an entry per output link (i.e. a list of pairs (l,min-hops)) This vector contains the minimum number of hops needed to reach a group member via the link If a link does not reach a group member (not on tree) use infinity for # hops. If a packet is received from S to G, The packet is sent over all links such that the time-to-live of the packet is at least the link’s entry in min-hops If no cache-entry of (S,G) compute the tree on the fly (incurring delay) Cache entries are not timed-out, they are just flushed out if new ones are needed (or when the network graph changes)

Related presentations


Other presentations created by Alien

Physical Security Lecture
05. 01. 2008
0 views

Physical Security Lecture

GREEK THEATRE
15. 10. 2007
0 views

GREEK THEATRE

Singapore National Symbols
14. 09. 2007
0 views

Singapore National Symbols

Origins of the Cold War
23. 12. 2007
0 views

Origins of the Cold War

CG43SlideSet
30. 04. 2008
0 views

CG43SlideSet

kaiser pres
28. 04. 2008
0 views

kaiser pres

GoldDifferences
22. 04. 2008
0 views

GoldDifferences

visn8
17. 04. 2008
0 views

visn8

Nov24 Regulatory approaches
16. 04. 2008
0 views

Nov24 Regulatory approaches

dr rom
14. 04. 2008
0 views

dr rom

file 6943
13. 04. 2008
0 views

file 6943

The Peak Oil Context Tom Petrie
10. 04. 2008
0 views

The Peak Oil Context Tom Petrie

H106g
09. 04. 2008
0 views

H106g

JapaneseGeography
07. 04. 2008
0 views

JapaneseGeography

Hamburg 2007
14. 09. 2007
0 views

Hamburg 2007

lfg
14. 09. 2007
0 views

lfg

Eddie Final Presentation
14. 09. 2007
0 views

Eddie Final Presentation

chalmers
14. 09. 2007
0 views

chalmers

The Rain Forest Final
14. 09. 2007
0 views

The Rain Forest Final

ECAKnowledgeFair
12. 10. 2007
0 views

ECAKnowledgeFair

Ch18part1
15. 10. 2007
0 views

Ch18part1

WNV AVB 02212006
21. 10. 2007
0 views

WNV AVB 02212006

giraffe pp
14. 09. 2007
0 views

giraffe pp

giraffe powerpoint
14. 09. 2007
0 views

giraffe powerpoint

giraffe
14. 09. 2007
0 views

giraffe

COOL STUFF ABOUT GIRAFFES
14. 09. 2007
0 views

COOL STUFF ABOUT GIRAFFES

ub041104
23. 10. 2007
0 views

ub041104

STORY OF THEME AND PLOT
23. 10. 2007
0 views

STORY OF THEME AND PLOT

PhiladelphiaZooPPP
14. 09. 2007
0 views

PhiladelphiaZooPPP

qu10 11
01. 12. 2007
0 views

qu10 11

Angelos CME Energetics
02. 11. 2007
0 views

Angelos CME Energetics

pptPanama s
22. 10. 2007
0 views

pptPanama s

hirotani
13. 11. 2007
0 views

hirotani

bon2003 mpls
29. 10. 2007
0 views

bon2003 mpls

PROF AZZA
23. 10. 2007
0 views

PROF AZZA

Fenton
29. 10. 2007
0 views

Fenton

Countering Offshore
29. 12. 2007
0 views

Countering Offshore

walters082902
23. 11. 2007
0 views

walters082902

razbash
26. 11. 2007
0 views

razbash

One 783Ngupta
04. 01. 2008
0 views

One 783Ngupta

Chapter 18 PPT
22. 10. 2007
0 views

Chapter 18 PPT

History of NAIS John Wiemers
20. 08. 2007
0 views

History of NAIS John Wiemers

BSP2D
14. 09. 2007
0 views

BSP2D

costarica1 ftparraud
22. 10. 2007
0 views

costarica1 ftparraud

mcmc2000a
06. 11. 2007
0 views

mcmc2000a

050317lc
16. 11. 2007
0 views

050317lc

ALA2003 OAI
04. 10. 2007
0 views

ALA2003 OAI

fwing
22. 10. 2007
0 views

fwing

acute 060727 transfusionmed
23. 10. 2007
0 views

acute 060727 transfusionmed

bckexpk3b
09. 07. 2007
0 views

bckexpk3b

anorexia
09. 07. 2007
0 views

anorexia

070207 Adjektiv
09. 07. 2007
0 views

070207 Adjektiv

A Brachmann
09. 10. 2007
0 views

A Brachmann

mueller jun07
19. 10. 2007
0 views

mueller jun07

Late Classic Maya Collapse
16. 02. 2008
0 views

Late Classic Maya Collapse

ISLAS GALAPAGOS
14. 09. 2007
0 views

ISLAS GALAPAGOS

Heatingoilwebsection ppp
24. 02. 2008
0 views

Heatingoilwebsection ppp

PIndustrialTrucks
26. 02. 2008
0 views

PIndustrialTrucks

ethanap
14. 09. 2007
0 views

ethanap

Propulsion CEV
07. 11. 2007
0 views

Propulsion CEV

MichelleWatt
20. 02. 2008
0 views

MichelleWatt

newsletterfall04
11. 03. 2008
0 views

newsletterfall04

EC T9 2008 Conference Proposal
12. 03. 2008
0 views

EC T9 2008 Conference Proposal

drugstatistics
17. 12. 2007
0 views

drugstatistics

icfa chep06
23. 10. 2007
0 views

icfa chep06

Hubert CW8
14. 09. 2007
0 views

Hubert CW8

A mi Papi 2089
19. 06. 2007
0 views

A mi Papi 2089

An ode to Mothers
19. 06. 2007
0 views

An ode to Mothers

LoffPresentation
17. 10. 2007
0 views

LoffPresentation

Maschera
19. 06. 2007
0 views

Maschera

manual
19. 06. 2007
0 views

manual

Luces De Navidad 1848
19. 06. 2007
0 views

Luces De Navidad 1848

leer
19. 06. 2007
0 views

leer

Lean Six SigmaATL011706
19. 06. 2007
0 views

Lean Six SigmaATL011706

lexisnexis
05. 10. 2007
0 views

lexisnexis

OAT Presentation v5
19. 06. 2007
0 views

OAT Presentation v5

moscatelli
19. 06. 2007
0 views

moscatelli

moon split
19. 06. 2007
0 views

moon split

money plus
19. 06. 2007
0 views

money plus

MKCL
19. 06. 2007
0 views

MKCL

Journey of the Spirit Lesson 6
01. 10. 2007
0 views

Journey of the Spirit Lesson 6

2 Jornada BISHOP
10. 10. 2007
0 views

2 Jornada BISHOP

No esperes
19. 06. 2007
0 views

No esperes

Amores locos 1992
19. 06. 2007
0 views

Amores locos 1992

College English book 2 Unit 7
24. 02. 2008
0 views

College English book 2 Unit 7

A vista de pajaro II 2109
19. 06. 2007
0 views

A vista de pajaro II 2109

Ammosov Vladimir ammosov pra
12. 10. 2007
0 views

Ammosov Vladimir ammosov pra

Amber la mejor de todas
19. 06. 2007
0 views

Amber la mejor de todas

CP317 lecture 6 Huck II 05
11. 12. 2007
0 views

CP317 lecture 6 Huck II 05

AHQA031204Mck
09. 07. 2007
0 views

AHQA031204Mck

Evergreen
03. 01. 2008
0 views

Evergreen

04 NJIT3
02. 01. 2008
0 views

04 NJIT3

Poster A4 Glasgow nov04
04. 10. 2007
0 views

Poster A4 Glasgow nov04

Ally McBeal
09. 07. 2007
0 views

Ally McBeal

sara paige
14. 09. 2007
0 views

sara paige

36181003
24. 10. 2007
0 views

36181003

MusicApprecBaroque 2
22. 11. 2007
0 views

MusicApprecBaroque 2

ELE386 Malware
20. 08. 2007
0 views

ELE386 Malware

RohanShah
12. 10. 2007
0 views

RohanShah

1022MAS net big picture
03. 01. 2008
0 views

1022MAS net big picture

Lo Suficiente 1744
19. 06. 2007
0 views

Lo Suficiente 1744

gm3 jp item14 Mangrove ITTO
22. 10. 2007
0 views

gm3 jp item14 Mangrove ITTO

2005AuditResults
09. 07. 2007
0 views

2005AuditResults

HABIC1 summary
17. 11. 2007
0 views

HABIC1 summary

aro ald informalsession
24. 10. 2007
0 views

aro ald informalsession

etu ambassadeurs juin 07 en
13. 03. 2008
0 views

etu ambassadeurs juin 07 en

Gobert poster
03. 10. 2007
0 views

Gobert poster

Kistenev
15. 11. 2007
0 views

Kistenev

6 History of Chemistry I
12. 10. 2007
0 views

6 History of Chemistry I

Jan2000report
04. 01. 2008
0 views

Jan2000report

course 4
03. 01. 2008
0 views

course 4