Cracking the coding interview--Q17.2

February 4, 2013
作者:Hawstein
出处:http://hawstein.com/posts/17.2.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Explain any common routing protocol in detail. For example: BGP, OSPF, RIP.

译文:

介绍常用路由协议。例如:BGP,OSPF,RIP

解答

这个可以根据具体以后从事职位与其的相关度做不同程度的了解。这里只做一个简单介绍。

BGP: Border Gateway Protocol (边界网关协议)

BGP是互联网上的一个核心路由协议。当BGP路由器第一次出现在互联网上时, 它会与那些和它能直接通信的其它BGP路由器建立连接。建立连接后的第一件事, 是从它相邻的路由器下载整个路由表。做完这件事后, 它与其它路由器就只需要交换少量更新信息即可。

BGP路由器通过发送和更新消息来表示到达给定IP地址的计算机的首选路径的变化。 如果一个BGP路由器发现一条新的更好的路径,它将更新自己的路由表, 并向与它直接连接的BGP路由器传播这个信息。 这些BGP路由器将依次决定是否更新自己的路由表及传播这个信息。

参考资料:http://www.livinginternet.com/i/iw_route_egp_bgp.htm

RIP: Routing Information Protocol (路由信息协议)

RIP为局域网提供一个标准的IGP(内部网关协议)协议,它提供了非常好的网络稳定性, 可以保证当一个网络连接断开时,能快速地由另一个网络连接进行包的发送。

RIP的工作倚仗于一个路由数据库,其中保存了计算机之间的快速路由信息。 每次更新中,每一个路由器会去告诉其它路由器它认为哪条路由是最快的。 更新算法将保证每个路由会用与相邻路由通信得到的最快路由去更新它的数据库。

参考资料:http://www.livinginternet.com/i/iw_route_igp_rip.htm

OSPF: Open Shortest Path First (开放式最短路径优先协议)

OSPF是一个特别高效的IGP路由协议。它比RIP要快,但也更复杂。

OSPF和RIP的主要区别是:RIP只保存到达目标地址的下一跳路由的信息; 而OSPF保存了局域网内所有连接的拓扑结构。OSPF算法描述如下:

  1. 开始。当一个路由被打开,它向所有的邻居发送”hello”的数据包, 然后接收它们返回的”hello”包。如果它的邻接路由同意同步, 那么它们将建立连接并同步数据库。

  2. 更新。每隔一定的时间间隔,每个路由发送一个更新信息给其它路由。 这个更新信息叫“连接状态”,用于向其它路由描述当前路由的数据库信息。 这样一来,所有的路由都将保存相同的局域网拓扑描述。

  3. 最短路径树。每个路由会计算一个数据结构叫“最短路径树” 用于描述到达目标地址的最短路径。这样一来,在每次通信中就知道哪个路由是最近的。

参考资料:http://www.livinginternet.com/i/iw_route_igp_ospf.htm

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview