Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older editNewer edit →
No edit summary
mNo edit summary
Line 1: Line 1:
In [[linear algebra]], the '''quotient''' of a [[vector space]] ''V'' by a [[linear subspace|subspace]] ''N'' is a vector space obtained by "collapsing" ''N'' to zero. The space obtained is called a '''quotient space''' and is denoted ''V''/''N'' (read ''V'' mod ''N'' or ''V'' by ''N'').
The '''Virtual Router Redundancy Protocol''' ('''VRRP''') is a computer networking protocol  that provides for automatic assignment of available [[Internet Protocol]] (IP) routers to participating hosts. This increases the availability and reliability of routing paths via automatic [[default gateway]] selections on an IP [[subnetwork]].


== Definition ==
The protocol achieves this by creation of virtual routers, which are an abstract representation of multiple routers, i.e. master and backup [[router (computing)|router]]s, acting as a group. The default gateway of a participating host is assigned to the virtual router instead of a physical router. If the physical router that is [[routing]] packets on behalf of the virtual router fails, another physical router is selected to automatically replace it. The physical router that is forwarding packets at any given time is called the master router.
Formally, the construction is as follows {{harv|Halmos|1974|loc=§21-22}}. Let ''V'' be a [[vector space]] over a [[field (mathematics)|field]] ''K'', and let ''N'' be a [[linear subspace|subspace]] of ''V''. We define an [[equivalence relation]] ~ on ''V'' by stating that ''x'' ~ ''y'' if ''x'' − ''y'' ∈ ''N''. That is, ''x'' is related to ''y'' if one can be obtained from the other by adding an element of ''N''. From this definition, one can deduce that any element of ''N'' is related to the zero vector; in other words all the vectors in ''N'' get mapped into the equivalence class of the zero vector.


The [[equivalence class]] of ''x'' is often denoted
VRRP provides information on the state of a router, not the routes processed and exchanged by that router.  Each VRRP instance is limited, in scope, to a single subnet. It does not advertise [[Internet Protocol|IP]] routes beyond that subnet or affect the [[routing]] table in any way.
:[''x''] = ''x'' + ''N''
since it is given by
:[''x''] = {''x'' + ''n'' : ''n'' ∈ ''N''}.


The quotient space ''V''/''N'' is then defined as ''V''/~, the set of all equivalence classes over ''V'' by ~. Scalar multiplication and addition are defined on the equivalence classes by
VRRP can be used in [[Ethernet]], [[Multiprotocol Label Switching|MPLS]] and [[token ring]] networks with [[IPv4|Internet Protocol Version 4]] (IPv4), as well as [[IPv6]].
*α[''x''] = [α''x''] for all α ∈ ''K'', and
*[''x''] + [''y''] = [''x''+''y''].
It is not hard to check that these operations are [[well-defined]] (i.e. do not depend on the choice of representative). These operations turn the quotient space ''V''/''N'' into a vector space over ''K'' with ''N'' being the zero class, [0].


The mapping that associates to ''v'' ∈ ''V'' the equivalence class [''v''] is known as the '''quotient map'''.
The protocol is described in IETF publication RFC 5798, which is an open standard, but a similar protocol with essentially the same facility is allegedly patented and licensed.<ref>[http://www.ietf.org/ietf-ftp/IPR/VRRP-CISCO IETF source]</ref>


== Examples ==
==Implementation==
Let ''X''&nbsp;=&nbsp;'''R'''<sup>2</sup> be the standard Cartesian plane, and let ''Y'' be a line through the origin in ''X''. Then the quotient space ''X''/''Y'' can be identified with the space of all lines in ''X'' which are parallel to ''Y''. That is to say that, the elements of the set ''X''/''Y'' are lines in ''X'' parallel to ''Y''.  This gives one way in which to visualize quotient spaces geometrically.
A virtual router must use 00-00-5E-00-01-XX as its [[Media Access Control]] (MAC) address. The last byte of the address (XX) is the Virtual Router IDentifier (VRID), which is different for each virtual router in the network. This address is used by only one physical router at a time, and it will reply with this MAC address when an ARP request is sent for the virtual router's IP address. Physical routers within the virtual router must communicate within themselves using packets with [[Multicast address|multicast]] [[Internet Protocol|IP]] address 224.0.0.18 and IP protocol number 112.<ref>[http://tools.ietf.org/html/rfc3768#section-5.2 Section 5.2.4.  Protocol]</ref>


Another example is the quotient of '''R'''<sup>''n''</sup> by the subspace spanned by the first ''m'' standard basis vectors. The space '''R'''<sup>''n''</sup> consists of all ''n''-tuples of real numbers (''x''<sub>1</sub>,…,''x''<sub>''n''</sub>).  The subspace, identified with '''R'''<sup>''m''</sup>, consists of all ''n''-tuples such that only the first ''m'' entries are non-zero: (''x''<sub>1</sub>,…,''x''<sub>''m''</sub>,0,0,…,0). Two vectors of '''R'''<sup>''n''</sup> are in the same congruence class modulo the subspace if and only if they are identical in the last ''n''&minus;''m'' coordinates. The quotient space  '''R'''<sup>''n''</sup>/ '''R'''<sup>''m''</sup> is [[isomorphic]] to  '''R'''<sup>''n''&minus;''m''</sup> in an obvious manner.
Routers have a priority of between 1-255 and the router with the highest priority will become the master. When a planned withdrawal of a master router is to take place, its priority can be lowered which means a backup router will pre-empt the master router status rather than having to wait for the hold time to expire. This reduces the black hole period.


More generally, if ''V'' is an (internal) [[direct sum of vector spaces|direct sum]] of subspaces ''U'' and ''W'':
==Elections of master routers==
:<math>V=U\oplus W</math>
A failure to receive a multicast packet from the master router for a period longer than three times the advertisement timer causes the backup routers to assume that the master router is dead. The virtual router then transitions into an unsteady state and an election process is initiated to select the next master router from the backup routers. This is fulfilled through the use of multicast packets.
then the quotient space ''V''/''U'' is naturally isomorphic to ''W'' {{harv|Halmos|1974|loc=Theorem 22.1}}.


An important example of a functional quotient space is a [[Lp_space#Lp_spaces|L<sup>p</sup> space]].
Backup router(s) are only supposed to send multicast packets during an election process. One exception to this rule is when a physical router is configured with a higher priority than the current master, which means that on connection to the network it will preempt the master status. This allows a system administrator to force a physical router to the master state immediately after [[booting]], for example when that particular router is more powerful than others within the virtual router. The backup router with the highest priority becomes the master router by raising its priority above that of the current master. It will then take responsibility for routing packets sent to the virtual gateway's MAC address. In cases where backup routers all have the same priority, the backup router with the highest IP address becomes the master router.


== Properties ==
All physical routers acting as a virtual router must be in the same LAN segment. Communication within the virtual router takes place periodically. This period can be adjusted by changing advertisement interval timers. The shorter the advertisement interval, the shorter the black hole period, though at the expense of more traffic in the network. Security is achieved by responding only to first hop packets, though other mechanisms are provided to reinforce this, particularly against local attacks. Election process is made orderly through the use of [[skew time]], derived from a router's priority and used to reduce the chance of the [[thundering herd problem]] occurring during election. The [[skew time]] is given by the formula <math>1 - \frac{Priority}{256}</math> (expressed in milliseconds).


There is a natural [[epimorphism]] from ''V'' to the quotient space ''V''/''U'' given by sending ''x'' to its equivalence class [''x'']. The [[kernel (algebra)|kernel]] (or [[nullspace]]) of this epimorphism is the subspace ''U''. This relationship is neatly summarized by the [[short exact sequence]]
Backup router utilization can be improved by load sharing. For more on this, see RFC 3768.
:<math>0\to U\to V\to V/U\to 0.\,</math>


If ''U'' is a subspace of ''V'', the [[dimension (vector space)|dimension]] of ''V''/''U'' is called the '''[[codimension]]''' of ''U'' in ''V''. Since a basis of ''V'' may be constructed from a basis ''A'' of ''U'' and a basis ''B'' of ''V''/''U'' by adding a representative of each element of ''B'' to ''A'', the dimension of ''V'' is the sum of the dimensions of ''U'' and ''V''/''U''. If ''V'' is [[finite-dimensional]], it follows that the codimension of ''U'' in ''V'' is the difference between the dimensions of ''V'' and ''U'' {{harv|Halmos|1974|loc=Theorem 22.2}}:
==History==
:<math>\mathrm{codim}(U) = \dim(V/U) = \dim(V) - \dim(U).</math>
VRRP is based on Cisco's proprietary [[Hot Standby Router Protocol]] (HSRP) concepts. The protocols, while similar in concept, are not compatible. Therefore, on newer installations VRRP is usually implemented, because it is the standard and is supported by many router and switch products.


Let ''T'' : ''V'' &rarr; ''W'' be a [[linear operator]]. The kernel of ''T'', denoted ker(''T''), is the set of all ''x'' &isin; ''V'' such that ''Tx'' = 0. The kernel is a subspace of ''V''. The [[first isomorphism theorem]] of linear algebra says that the quotient space ''V''/ker(''T'') is isomorphic to the image of ''V'' in ''W''. An immediate corollary, for finite-dimensional spaces, is the [[rank-nullity theorem]]: the dimension of ''V'' is equal to the dimension of the kernel (the ''nullity'' of ''T'') plus the dimension of the image (the ''rank'' of ''T'').
* (Cisco Example) '''VLAN Tagging'''


The [[cokernel]] of a linear operator ''T'' : ''V'' &rarr; ''W'' is defined to be the quotient space ''W''/im(''T'').
track 1 interface Serial0/0/0.1 ip routing      ! Points at the interface that needs to be Prioritized
 
  interface fastethernet0/0.1                    ! VLANs have to be on a Sub-Interface, It is best practice to match the Sub-Interface # and the VLAN #
== Quotient of a Banach space by a subspace ==
  encapsulation dot1q 1                        ! Enables IEEE 802.1Q VLAN frame tagging, followed by the VLAN # that this sub-interface will route
If ''X'' is a [[Banach space]] and ''M'' is a [[closed set|closed]] subspace of ''X'', then the quotient ''X''/''M'' is again a Banach space. The quotient space is already endowed with a vector space structure by the construction of the previous section. We define a norm on ''X''/''M'' by
  ip address x.x.x.x 255.255.255.0              ! Make sure the IP is on the same subnet as the virtual Gateway1 
:<math> \| [x] \|_{X/M} = \inf_{m \in M} \|x-m\|_X. </math>
  vrrp 1 priority 110                          ! The Priority of the Gateway1
The quotient space ''X''/''M'' is [[complete space|complete]] with respect to the norm, so it is a Banach space.
  vrrp 1 ip <Gateway1>                         ! The Virtual Gateway for the VLAN 1
 
  vrrp 1 preempt delay minimum 20              ! If the other router fails it will wait 20 sec before becoming the master
=== Examples ===
  vrrp 1 track 1 decrement 15                  ! If the S0/0/0.1 Link fails, This command drops the priority by 15
Let ''C''[0,1] denote the Banach space of continuous real-valued functions on the interval [0,1] with the [[sup norm]]. Denote the subspace of all functions ''f'' &isin; ''C''[0,1] with ''f''(0) = 0 by ''M''. Then the equivalence class of some function ''g'' is determined by its value at 0, and the quotient space ''C''[0,1]&nbsp;/&nbsp;''M'' is isomorphic to '''R'''.
!
 
  interface fastethernet0/0.5                    ! VLANs have to be on a Sub-Interface, It is best practice to match the Sub-Interface # and the VLAN #
If ''X'' is a [[Hilbert space]], then the quotient space ''X''/''M'' is isomorphic to the [[Hilbert space#Orthogonal complements and projections|orthogonal complement]] of ''M''.
  encapsulation dot1q 5                        ! Enables IEEE 802.1Q VLAN frame tagging, followed by the VLAN # that this sub-interface will route
 
  ip address x.x.x.x 255.255.255.0              ! Make sure the IP is on the same subnet as the virtual Gateway2 
=== Generalization to locally convex spaces ===
  vrrp 5 priority 110                          ! The Priority of the Gateway2
The quotient of a [[locally convex space]] by a closed subspace is again locally convex {{harv|Dieudonné|1970|loc=12.14.8}}. Indeed, suppose that ''X'' is locally convex so that the topology on ''X'' is generated by a family of [[seminorm]]s {''p''<sub>&alpha;</sub>|&alpha;&isin;''A''} where ''A'' is an index set. Let ''M'' be a closed subspace, and define seminorms ''q''<sub>&alpha;</sub> by on ''X''/''M''
  vrrp 5 ip <Gateway2>                         ! The Virtual Gateway for the VLAN 5
 
  vrrp 5 preempt delay minimum 20              ! If the other router fails it will wait 20 sec before becoming the master
:<math>q_\alpha([x]) = \inf_{x\in [x]} p_\alpha(x).</math>
  vrrp 5 track 1 decrement 15                  ! If the Fa0/0.5 Link fails, This command drops the priority by 15
 
!
Then ''X''/''M'' is a locally convex space, and the topology on it is the [[quotient topology]].
  router bgp <ASN>
 
  network <Gateway1> mask 255.255.255.0        ! Broadcasts Gateway1 out the WAN through BGP
If, furthermore, ''X'' is [[metrizable]], then so is ''X''/''M''.  If ''X'' is a [[Fréchet space]], then so is ''X''/''M'' {{harv|Dieudonné|1970|loc=12.11.3}}.
  network <Gateway2> mask 255.255.255.0        ! Broadcasts Gateway2 out the WAN through BGP


==See also==
==See also==
*[[quotient set]]
* [[Common Address Redundancy Protocol]] (CARP) - A non-proprietary, patent-free, and unrestricted alternative to HSRP and VRRP.
*[[quotient group]]
* [[Gateway Load Balancing Protocol]] -  A [[Cisco Systems]] proprietary router redundancy protocol providing load balancing
*[[quotient module]]
* [[Hot Standby Routing Protocol]] -  A [[Cisco Systems]] proprietary router redundancy protocol
*[[quotient space]] (in [[topology]])
* [[R-SMLT]] (Routed Split Multilink Trunking) - An [[Avaya]] proprietary router redundancy and router load balancing  protocol - replacement for VRRP in Avaya core networks
* [[SMLT]] An [[Avaya]] redundancy protocol
* [[First Hop Redundancy Protocols]] - Lists of default gateway redundancy protocols


==References==
==References==
* {{citation|first=Paul|last=Halmos|authorlink=Paul Halmos|title=Finite dimensional vector spaces|publisher=Springer|year=1974|isbn=978-0-387-90093-3}}.
{{reflist}}
* {{citation|first=Jean|last=Dieudonné|authorlink=Jean Dieudonné|title=Treatise on analysis, Volume II|publisher=Academic Press|year=1970}}.
 
==External links==
* [http://www.keepalived.org/ Keepalived 1.2.x adds ipv6 support]
* [http://tools.ietf.org/html/rfc5798 The current VRRP RFC (RFC 5798 - VRRPv3 for IPv4 and IPv6) which obsoletes RFC3768]
* [http://www.ietf.org/mail-archive/web/vrrp/current/maillist.html The IETF VRRP mailing list archive]
* [http://www.redbooks.ibm.com/redpapers/pdfs/redp3657.pdf A detailed VRRP article]
* [http://kerneltrap.org/comment/reply/477/1567 Controversy involving VRRP and Cisco patents]
* [http://web.archive.org/web/20080625055935/http://www.hanetworks.com/networks/nokia/vrrp/analysis_of_vrrpv2.htm Analysis of VRRPv 2 Issues and Solutions]
* Implementations
** [http://sourceforge.net/projects/vrrpd/ A GPL licensed implementation of VRRP designed for Linux operating systems]
** [http://sourceforge.net/projects/svrrpd/ A BSD licensed implementation of VRRP for Unix-like operating systems] (described as "not functional yet")
** [http://www.keepalived.org A GPL licensed implementation of VRRPv2 for Linux operating systems]
** [http://www.cisco.com/en/US/docs/ios/ipapp/configuration/guide/ipapp_vrrp.html Configuring VRRP on Cisco IOS]
** [http://support.3com.com/infodeli/tools/bridrout/u_guides/html/nb111/family/features/vrrp.htm Configuring VRRP on 3com NETBuilder]
** [[Vyatta]], a commercial open-source router / firewall with VRRP functionality.
** [http://www.jbm-web.com/cart/index.php?main_page=product_info&cPath=67&products_id=184 JBM C120 - A cellular enabled enterprise class router]


[[Category:Linear algebra]]
[[Category:Internet protocols]]
[[Category:Functional analysis]]
[[Category:Routing protocols]]


[[ca:Espai vectorial quocient]]
[[de:Virtual Router Redundancy Protocol]]
[[de:Faktorraum]]
[[es:Virtual Router Redundancy Protocol]]
[[it:Spazio vettoriale quoziente]]
[[fr:Virtual Router Redundancy Protocol]]
[[he:מרחב מנה (אלגברה לינארית)]]
[[ja:Virtual Router Redundancy Protocol]]
[[ja:商線型空間]]
[[ru:VRRP]]
[[pl:Przestrzeń ilorazowa (algebra liniowa)]]
[[ru:Факторпространство по подпространству]]
[[zh:商空间 (线性代数)]]

Revision as of 23:05, 12 August 2014

The Virtual Router Redundancy Protocol (VRRP) is a computer networking protocol that provides for automatic assignment of available Internet Protocol (IP) routers to participating hosts. This increases the availability and reliability of routing paths via automatic default gateway selections on an IP subnetwork.

The protocol achieves this by creation of virtual routers, which are an abstract representation of multiple routers, i.e. master and backup routers, acting as a group. The default gateway of a participating host is assigned to the virtual router instead of a physical router. If the physical router that is routing packets on behalf of the virtual router fails, another physical router is selected to automatically replace it. The physical router that is forwarding packets at any given time is called the master router.

VRRP provides information on the state of a router, not the routes processed and exchanged by that router. Each VRRP instance is limited, in scope, to a single subnet. It does not advertise IP routes beyond that subnet or affect the routing table in any way.

VRRP can be used in Ethernet, MPLS and token ring networks with Internet Protocol Version 4 (IPv4), as well as IPv6.

The protocol is described in IETF publication RFC 5798, which is an open standard, but a similar protocol with essentially the same facility is allegedly patented and licensed.[1]

Implementation

A virtual router must use 00-00-5E-00-01-XX as its Media Access Control (MAC) address. The last byte of the address (XX) is the Virtual Router IDentifier (VRID), which is different for each virtual router in the network. This address is used by only one physical router at a time, and it will reply with this MAC address when an ARP request is sent for the virtual router's IP address. Physical routers within the virtual router must communicate within themselves using packets with multicast IP address 224.0.0.18 and IP protocol number 112.[2]

Routers have a priority of between 1-255 and the router with the highest priority will become the master. When a planned withdrawal of a master router is to take place, its priority can be lowered which means a backup router will pre-empt the master router status rather than having to wait for the hold time to expire. This reduces the black hole period.

Elections of master routers

A failure to receive a multicast packet from the master router for a period longer than three times the advertisement timer causes the backup routers to assume that the master router is dead. The virtual router then transitions into an unsteady state and an election process is initiated to select the next master router from the backup routers. This is fulfilled through the use of multicast packets.

Backup router(s) are only supposed to send multicast packets during an election process. One exception to this rule is when a physical router is configured with a higher priority than the current master, which means that on connection to the network it will preempt the master status. This allows a system administrator to force a physical router to the master state immediately after booting, for example when that particular router is more powerful than others within the virtual router. The backup router with the highest priority becomes the master router by raising its priority above that of the current master. It will then take responsibility for routing packets sent to the virtual gateway's MAC address. In cases where backup routers all have the same priority, the backup router with the highest IP address becomes the master router.

All physical routers acting as a virtual router must be in the same LAN segment. Communication within the virtual router takes place periodically. This period can be adjusted by changing advertisement interval timers. The shorter the advertisement interval, the shorter the black hole period, though at the expense of more traffic in the network. Security is achieved by responding only to first hop packets, though other mechanisms are provided to reinforce this, particularly against local attacks. Election process is made orderly through the use of skew time, derived from a router's priority and used to reduce the chance of the thundering herd problem occurring during election. The skew time is given by the formula 1−Priority256 (expressed in milliseconds).

Backup router utilization can be improved by load sharing. For more on this, see RFC 3768.

History

VRRP is based on Cisco's proprietary Hot Standby Router Protocol (HSRP) concepts. The protocols, while similar in concept, are not compatible. Therefore, on newer installations VRRP is usually implemented, because it is the standard and is supported by many router and switch products.

  • (Cisco Example) VLAN Tagging
track 1 interface Serial0/0/0.1 ip routing      ! Points at the interface that needs to be Prioritized 
 interface fastethernet0/0.1                    ! VLANs have to be on a Sub-Interface, It is best practice to match the Sub-Interface # and the VLAN #
  encapsulation dot1q 1                         ! Enables IEEE 802.1Q VLAN frame tagging, followed by the VLAN # that this sub-interface will route
  ip address x.x.x.x 255.255.255.0              ! Make sure the IP is on the same subnet as the virtual Gateway1   
  vrrp 1 priority 110                           ! The Priority of the Gateway1
  vrrp 1 ip <Gateway1>                          ! The Virtual Gateway for the VLAN 1
  vrrp 1 preempt delay minimum 20               ! If the other router fails it will wait 20 sec before becoming the master
  vrrp 1 track 1 decrement 15                   ! If the S0/0/0.1 Link fails, This command drops the priority by 15
!
 interface fastethernet0/0.5                    ! VLANs have to be on a Sub-Interface, It is best practice to match the Sub-Interface # and the VLAN #
  encapsulation dot1q 5                         ! Enables IEEE 802.1Q VLAN frame tagging, followed by the VLAN # that this sub-interface will route
  ip address x.x.x.x 255.255.255.0              ! Make sure the IP is on the same subnet as the virtual Gateway2   
  vrrp 5 priority 110                           ! The Priority of the Gateway2
  vrrp 5 ip <Gateway2>                          ! The Virtual Gateway for the VLAN 5
  vrrp 5 preempt delay minimum 20               ! If the other router fails it will wait 20 sec before becoming the master
  vrrp 5 track 1 decrement 15                   ! If the Fa0/0.5 Link fails, This command drops the priority by 15
!
 router bgp <ASN>
  network <Gateway1> mask 255.255.255.0         ! Broadcasts Gateway1 out the WAN through BGP
  network <Gateway2> mask 255.255.255.0         ! Broadcasts Gateway2 out the WAN through BGP

See also

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

External links

de:Virtual Router Redundancy Protocol es:Virtual Router Redundancy Protocol fr:Virtual Router Redundancy Protocol ja:Virtual Router Redundancy Protocol ru:VRRP

  1. ↑ IETF source
  2. ↑ Section 5.2.4. Protocol
Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=47799"