作者pinky94 (pinky)
看板Examination
标题[考题] 101调查局三等 电脑网路
时间Wed Nov 27 23:43:53 2013
[考题] 国考历届考题与考题观念讨论(书里看到的选这个)请附上想法、出处
出处:如题
若有一分封交换网路的网路设备位址是8位元,今假设有一路由器(router)
使用最长前缀匹配(longest prefix matching)的演算法则,且其设定的转送表
(forwarding table)为以下内容
Prefix Match Link Interface
0001 A
00111 B
0011 C
otherwise D
由於透过搜寻此表格以确认资料之转出介面(Link Interface)过於缓慢,
故一般做法拟将此表格内容改以树状结构储存,
以便利用树状结构之快速搜寻能力而加快确认资料转出介面的速度。
请设计出一个储存此表格内容之二元树状结构。(12分)
此外,请依此树状结构,说明若有两个资料封包(packet)
其目的位址分别是00111100与00011100时,
树状结构如何快速决定此两个资料封包之转出介面?
解法:
二元树的左子树配0,右子树配1,依据prefix match link 的值可以画出二元树
可是第二个问题要怎麽根据位址决定转出介面???
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 123.205.139.17
1F:→ kinglord:从根开始碰到0往左走 碰到1往右走 直到尽头就是最长匹配 11/28 00:22
2F:→ kinglord:的转出介面了 11/28 00:23