TW200803376A - MAC address management method - Google Patents

Description

200803376 九、發明說明： 【發明所屬之技術領域】 〜 本發明係有關於電腦網路，尤其是有關於媒體存取控 制位址（Media Access Control Address，MAC Address)管 理方法。 【先前技術】 第la圖係為習知的媒體存取控制位社表(Media Access

Control Table，MAC Table)。一般的網路裝置例如路由器或 父換益中，都會挺供一塊§己憶體以將所蒐集之媒體存取控 制位址（Media Access Control Address，MAC Address)記 錄至此記憶體上並建立一媒體存取控制位址表，若網路上 存在某些未被記錄之媒體存取控制位址，則能透過學習的 方式更新媒體存取控制位絲以記錄所有網路上所識別到 的媒體存取控制位址。如圖所*，媒體存取控制位址表可 以方便地管理與查詢所學習到的媒體存取控制位址，其 中，媒體存取控制位址表包含複數連續的攔位，如第一棚 位⑽、第二攔位1〇2、第三栅位，104與第四攔位1〇6 等等.··..，每一攔位皆能儲存一個媒體存取控制位址。此 媒體存取控制位址表中另鱗了每四個攔位的記憶體位址 以當成索引值’如mdexl為第一欄位1〇〇、第二欄位 1合〇2、第三攔位刚與第四攔位1〇6之素引值。所以藉由 索引值’可以快速檢索與存取媒體存取㈣位址。 f lb圖係為昏知.祕體:存麵制位址料 圖。右一塊記憶體觀臟包含為r値搁位,，.前記憶霞

Clienfs Docket No.：VIT-〇5.〇255 TT s Docket N〇.0608-A40659TW/final/YeatsLuo/5/30/2006 200803376 、、—有512個索引值’且每一索引值皆對應至四個棚位。 ，以在步驟漏中，當接收一個封包時，將此封包之媒體 存取控制位址經過-個雜湊運算（HASH) 管 體存取控制位址所屬的索引值。另外，㈣值的I生，也、 可以是從賴體存取控·址中取末九條光直接產生。 ，著，在步驟隨中’查詢此記憶體之媒體存取控制位址 斷在步驟S1〇2中所得之索引值所對應的四個攔位 中，疋否已經存在此媒體存取控制位址。如果不存在，則 進行步驟S108，透過-學習步驟，將此媒體存取控制位址 紀錄至此記憶體中以更新媒體存取控制位址表。然而，一 般來說’此媒體存取控制位址表中的每個媒體存取控制位 址=有-個逾時期限。如果某—個媒體存取控制位址超過 一定的時間未有存取的動作，則該媒體存取控制位址表從 對應的攔位中删除該媒體存取控制位址。所以在步驟si〇4 的檢查結果中，如果查到該媒體存取控制位址已經存在於 此媒體存取控制位址表中，則進行步驟Sl〇6，只要更新此 媒脸存取控制位址所對應的存取時間，使此媒體存取控制 位址保持在逾時期限之内。 第2a圖係為習知的媒體存取控制學習步驟的流程圖。 此學習步驟如下所述。首先，在步驟82〇2中，根據此媒體 存取控制位址所產生的索引值去搜尋此媒體存取控制位址 表中對應的四個攔位。在步驟S204中，逐一判斷此四個欄 位中是否有空間可供存放此爆體存取控制位址。&如果其私 一個攔位是有空間的，'則進行步驟S206，將此媒體存取控、 Clienfs Docket N〇.:VIT-05-0255 TT’s Docket Νο:0608-Α40659Ϊ^ίίηα1Α^ΐΛ〇/5/30/2006 200803376 制位址存放至有空間的攔位。如果四個搁位都 則^步驟S208’將此媒體存取控制位址覆寫至此四個攔 :覆f Γ則，可以選擇最接近逾時期限的欄 位’也可以疋四個攔位依序輪流，或是隨機犧牲此四個棚 位其中之一。 第2b圖係為習知的媒體存取控制位址表。圖上顯示索 引Indexl、IndeX2和Index3，各對應四個攔位。其中idd ⑩的四個欄位為第一攔位200、第二欄位2〇2、第三攔位 204與第四欄位206 ,且第一攔位2〇〇已儲存了媒體存取 控制位址（標示為learned)，而其他三個攔位是空的（標 示為empty)。索引lndex2的四個欄位為第五攔位2〇8、 第六欄位210、第七欄位212與第八攔位214且先前均 已填滿了媒體存取控制位址（learnecj)，當有對應至In(jex2 之一新的媒體存取控制位址要填入時，第五攔位2〇8就被 覆寫了（標示為overwrite)。而索引index3所對應的四個 _ 欄位為第九攔位—216、第十攔位218、第十一欄位220與 第十二攔位222，則全部都是空的。 雖然利用索引值可以报方便的檢索或存取四個或多個 相對應的媒體存取控制位址。然而這樣的媒體存取控制位 址管理方法，卻有技術上的缺點。在本例中可見，當Index2 的四個攔位都填滿時，若是再出現屬於Index2的媒體存取 控制位址，就必須進行覆寫，拋棄Index2的其中一欄位裏 的既有值。而事實上記憶體中還有很多空間沒有利用,.，例 如Index3的攔位仍有空間閒置。因此在記憶體還沒有充份v

Clienfs Docket No.:VIT-05-0255

TT5s Docket No:0608-A40659TW/fiiiaLYeatsLuo/5/30/2006 R 200803376 利用的情灯卻必_㈣錢體存取控制位减很不合 理的做法，導致無法有效利用資源。 【發明内容】 本發明提供一種—媒體存取控制位址（Media Access Control Add職，MAC Address) f理方法。此方法包含下

歹J y驟首先;^查一媒體存取控制位址表(MAC丨此^)内 對應到# f t引值之-第-攔位與—第二攔位之儲存空 間；接著，當此第一攔位與此第二攔位之儲存空 相對應之㈣絲㈣健，檢纽_存取控制位址表 :對應第一索引值之一第三攔位與一第四攔位之儲存 工間，最後，當此第三攔位或此第四攔位其中之一之儲存 空間為淨空m料儲存之媒體存取控制位址填入 此第三欄位與此第四攔位其中之一，其中，在此媒體存取 控制位址表内，此第二索引值接續此第一索引值之後。 本發明提供一種媒體存取控制位址管理方法，在某個 索引值所對應的攔位用完時，還能借用下—㈣值的搁仅 手儲存媒體存取控制位址，大大的增加了空閒欄位的利用 率首先’知:供一媒體存取控制位址表，包含複數連續的 欄位，每一攔位儲存一個媒體存取控制位址。其中的每一 索引值對應至少兩個攔位。當接收一網路封包時，查詢此 媒體存取控制位址表，判斷此鱗路封包中的媒體存取控制 位址是否已存在於此媒體存取控制位址表中。如果此媒體 存取控制位址不存在於此媒體存取控制位址表，則執行一 學習步驟，將此媒體存取控制位址紀錄在此媒體存取控制 CUenfs Docket No.:VIT.〇5.〇255 s Docket No:0608-A40659TW/fmalA"eatsLuo/5/30/2006 200803376 位址表中。 位：!首先根據此媒體存取控制 弟索引值，接著檢查此第一索引值對應的 、:u有空間。如果此第-索引值對應的攔也皆已填 位是否仍有〜ί 的H引值所對應的攔 右_ 丨果此第二索引值所對應的棚位之—仍 :媒：此媒體存取控制位址寫人此有空間的欄位。 纪釺每、控制位址表尚包含複數時戳攔位’可用來 制位址的閒置時間。在判斷此網路封 址mi 址是否已存在於此媒體存取控制位 、，匕耘中，如果此媒體存取控制位址已存在於此媒體 日^控制位址表，収新此媒體存取控難址對應的閒置 滿，ilUL如果此第二索引值所對應的攔位皆已填 二步驟，將此媒體存取控制值覆寫至此第 體索引對應的攔位其中之—。先前查詢此媒 體存取控·址表时.驟，係檢查此'第—索引值二 引值所對應的攔位中，是否存在此媒體存取控制位址。'、 、，=!的’如果此第二索引值所對應的攔位皆已填 :::檢，此第二索引值的-第三索引值所對應的攔 =否^填滿。如果此第三索引值所對應的攔位之一仍有. «體存取控·址寫入此有空間的搁位。而 存取控•址表的轉’即紐查此& 索引值、此第二索㈣以吸此第三㈣值所對應的棚心

Clienfs Docket N〇.:VIT-05-0255 TT5s Docket No:0608.A40659TW/finamatsLuo/5/30/2006 200803376 中，疋否存在此媒體存取控制位址。 ' 其中，根據此媒體存取控制位址運算出此第一索引值 的步驟，係取此媒體存取控制位址的末十位元，經雜湊運 异而得到此第一索引值。 【實施方式】 第3a圖係為本發明的媒體存取控制學習方法流程圖。’ 本發明提供一種一媒體存取控制位址（Media Access Control Address，MAC Address)管理方法。此方法包含下 列步驟。首先，在步驟S30中，當接收一個封包時，得到 將此封包之媒體存取控制位址所屬的第—索引值後，先檢 查媒體存取控制位址表(MAC table)内對應到第一索引 值之第一攔位與第二攔位是否仍有足夠的儲存空間，而在 本實施例裏，每個索引值可以是只對應兩個攔位，也可以 是四個或六個攔位。接著，在步驟S32中，當此第一攔位 與此第二欄位之儲存㈣皆填滿相對應之媒體存取控制位 址丄進而檢查此媒體存取控制位址表内對應到第二索引值 之第二攔位與第四攔位是否具有足夠之儲存空間。如果此 第三攔位與此第四攔位皆已填滿，則在步驟幻4中，更進 一步檢查此媒體存取控制位址表内對應到之第三索引值的 第五攔位與第六欄位是否仍有足夠的儲存空間，當此第五 攔位或此第六攔位其中之一之儲存空間為淨空狀=，則在 步驟S36中，亦能將此等待儲存之媒體存取控制^址殖入 ’其中’在此媒體存取 控制位址表内，此第三索引值接續此第二索引值之後。、

Client’s Docket N〇.:VIT-05-0255 TT5s Docket No:0608-A40659TW/fina]A^eatsLuo/5/30/2006 11 2UUH03376 相對應之媒體存第存空間皆填滿 覆寫步驟，亦即將此箅 在乂驟S39 +，進行一 此第-攔位、此第-們☆子之媒體存取控制位址覆寫至 位與此第六攔位::::之此第:欄位、此第四此第五攔 之每-欄位均桴=ΐ.!Γ。由於媒體存取控制位址表 取控制位址的閒置時^ 、，錢母一媒體存

窝最接近逾時期限的攔位，也可以是選擇覆 犧牲此些攔位其中之… 讀序輪流，或是隨機 方在步驟S30中，楚ipa ... 之儲在〜H 攔或此第二攔位其中之一 待狀態時，則如步驟S37所示，將此此等 位址填入此第-攔位與此第二攔位 中’此第三攔位或此第四攔位其 狀態時’則如步驟⑽所示，將 專ff存之媒體存取控制位址填入此第三欄位與此第四 攔位其中之一。 此外’如果此媒體存取控制位址已存.在於此媒體存取 &制位址表，則更新此媒體存取控·址對應的閒置時 即可。 第3b圖係為本發明的另—媒體存取控制學習方法流 程圖。本發明提供的媒體存取控制位址管理方法，可以在 某個索引值所對應的攔位用完時，借用下一索引值的棚位 來儲存媒n存取控齡n大的增加了m攔位的利用 率。在步驟S302中，根據此媒體存取控制值產生的索引值

Client’s Docket No.:VIT-05-0255 TT5s Docket No:0608-A40659TW/finai/YeatsLuo/5/30/2006 12 200803376 去=此媒體存取控制位址表中對應的複數棚位 施例中’母個时會可以是只嘴應兩個攔位,，也可以ΐΛ 丕右*門可户说Λ 中’逐一判斷此些攔位是 Γ ^ 進行步驟S3G6 ’將此媒體存取控二 址寫入此攔位。相對的，1 I 心 皆沒有m目丨 ㈣朗龍的所有攔位 心又有工間了，則跳至㈣_， 位’逐-判斷此些攔位是否有空間可存 位址。同樣的，如果此些攔位其中-個是有空間的子，= 行^驟測’將此媒體存取控制位址寫入此搁位。如果牛 驟S308中已經沒有空間了，則跳至步驟灿，進行一^ 寫程序。在覆寫程序中，此媒體存取控制位址可 = 步驟隨所檢絲的攔位其中之…至於要如何選擇= 哪-麵位，則可以是依照各種不同的原·定 可以選擇最接近逾時期限的欄位，也可以是依 是隨機犧牲此些欄位其中之—。更進L > 也可以選擇步驟S308所檢查過的攔位做為難取代 象。在本流程圖中，僅介紹了借用下一索引值的搁位，但 不限定於此。舉例來說，如果步驟S3〇8中檢查出沒有空間 了 ’也可以更進-步借用再下—個索引值的攔位，進 行檢查與寫入的步驟。 第4圖係為本發明實施例之一的媒體存取控制位址 表。每一個索弘值與應兩個攔位，而每個攔位各附有一時 戳值（依時間順序，命禽朴，赞，——_ Μ

Client’s Docket Νο·:νΤΓ-05-0255 TT^ Docket No:0608-A40659TW/fmal^eatsLuo/5/30/2006 13 200803376 每一欄位的更新時間，可以用來計算閒置時間，做為逾期 汰舊順序的判斷依據。時戳管理已有許多習知的做法，在 本實施例中不加詳述。在第4圖中，indexl的攔位為第一 攔位400與第二欄位402，且第一欄位400已填滿 (learned y而第二攔位402則是空的。如果一個屬於 Index2的媒體存取控制位址進來時，發現Index2的第三欄 位404與第四欄位406皆已填滿，則借用Index3的第五 • 攔位408來存放（標示為learned(2))。如果Index3的第 五攔位408與第六攔位410也存滿了，則進行覆寫，例 如寫回Index2的第三欄位404中（標示為〇verwrite(2))。 每個索引值皆可向下一個索引值借攔位，因此可看到，

Index3 向 Index4 借了兩個棚值，而 jndex4 向 in(jex5 借了 一個攔位。因為每一媒體存取控制值可能存放的範圍被擴 充了，所以大大的善用了可能閒置的空間。此外，也因為 每一媒體存取控制值可能存放的範圍跨越了不同的索引 ❿值’所以在第lb圖中提及的步驟si〇4，查詢媒體存取控 制位址表的方式’也要對應的改良。基本上索引值和攔位 的記憶體位址有對應關係，在記憶體中都是連續的，所以 在進行步驟S104的查詢時，就是把逐攔比對的步驟延續至 下一個索引值，依此類推。 第5圖係為本發明另一實施例的媒體存取控制位址表 示意圖。對於索引值IndexA而言，媒體存取控制位址可以 借用到下兩個索引值，』p IndexC:。因此万食昧放Jnde^ 對應的媒體存取控制值餘棚位標不為A。同理，可能存放〜

Client’s Docket No.:VIT-〇5-〇255 TT^ Docket No:0608-A40659TW/fmal^eatsLuo/5/30/2006 200803376

IndexB對應的媒體存取控制值的攔位標示為b。因此在 對應的中，可能存放的親存取控制位址就包 3 了 A B和C二種。同樣的，這種媒體存取控制位址表 對應的查.旬方式也會需要些許對應的調整。舉例來說，A 可此存放在IndexA、IndexB和indexc所對應的所有攔位 中所以為了查5旬A，就必須搜遍IndexA、IndexB和 所對應的所有攔位。在本實施例中每個索引值對應兩個搁 •位。但也可以是其他的數目，並不限定於此。索引值的產 生，可Γ是取此媒體存取控制位址的末十位元直接當成索 引’或是將此媒體存取控制位址經雜湊運算轉換成一個十 位元的數值。 【圖式簡單說明】 第la圖係為習知的媒體存取控制位址表； f lb圖係為習知的媒體存取控制管理方法流程圖； f 2a圖係為習知的媒體存取控制學習方法流程圖； 籲 f 2b圖係為習知的另__媒體存取控制位址表； ' 第3a圖係為本發明的媒體存取控制學習方法流程圖； 第3b圖係為本發明的另一媒體存取控制學習方法流 程圖； 第4圖係為本發明實施例之一的媒體存取控制位址 表；以及 第5圖係為本發明另一實施例的媒體存取控制位址表 示意圖。 * 【主要元件符號說明】 少”…-

Client’s Docket No.:VIT-〇5-〇255 ΊΤ^ Docket No:0608.A40659TW/finalAfeatsLuo/5/30/2006 15 200803376 第二攔位、 :100、102、104、106〜屬於 Indexl 之第一攔位 第三攔位與第四攔位 外⑽、110、112、114〜屬於Index2之第五欄位、第六搁位、 弟七欄位與第八欄位 —116、118、120、122〜屬於11^3之第九欄位、第十攔位、 第十一攔位與第十二攔位 〆、202、204、邊於Indexl之第一搁位、第二搁位、 第二攔位與第四攔位 弟六搁位、 2〇8、210、212、214〜屬於111(1沒2之第五攔位 第七攔位與第八攔位 216、218、22G、222〜屬於In細3之第九攔位、第十攔位、 弟十一攔位與第十二攔位 400、402〜屬於Indexl之第一攔位與第二攔位 404、406〜屬於Index2之第三攔位與第四攔位

408、410〜屬於1]1(1找3之弟五搁>[立與第六搁位 412、414〜屬於Index4之第七攔位與第八攔位 416、418〜屬於111(1找5之弟九搁位與第十棚位

Client’s Docket N〇.:VIT-05-0255 TT，s Docket No:0608-A40659TW/fmal/YeatsLuo/5/30/2006 16

Claims (1)

1. 200803376 十、申請專利範圍： 1·媒體存取控制位址（Me(jia Access Control Address, MAC Address)管理方法，包含下列步驟： 檢查一媒體存取控制位址表（Media Access Control Table, MAC Table)内對應到一第一索引值之一第一攔位與 一第二欄位之儲存空間； 當該第一欄位與該第二攔位之儲存空間皆填滿相對應 ⑩之媒體存取控制位址，檢查該媒體存取控制位址表内對應 到第一索引值之一苐二攔位與一第四攔位之儲存空間； 以及 當該第三欄位或該第四攔位其中之一之儲存空間為淨 空狀態，將一等待儲存之媒體存取控制位址填入該第三攔 位與該第四攔位其中之一； 其中，在該媒體存取控制位址表内，該第二索引值接 續該第一索引值之後。 • 2.如申請專利範圍第1項所述的方法，其中該媒體存 取控制位址表更進一步包含複數時戳播位，以 媒體存取控制位址的閒置時間。 3·如申請專利範圍第i項所述的方法，其中更進一步 包含，如果該媒體存取控制位址已存在於該媒體存取控^ 位址表，則更新該媒體存取控制位址對應的閒置時間。 4·如申請專利範圍第1項所述的方法，其中芝進一步 包含，將該等待儲存之媒體存取控制位址填入該第一攔位 與該第二攔位其中之―，當該第η欄仇或該第二欄位^中^ Client’s Docket Νο·:ΥΠ；〇5-〇255 TT>s Docket N〇：0608.A40659IW/finayYeatsLuo/5/30/2006 17 200803376 之一之儲存空間為淨空狀態。 包含專利_第1項所述的方法，其―更進-步 果該弟二攔位與該第四攔位皆已填滿，目,丨％/ 驟^^特儲存之媒體存取控制位址覆 攔位、該弟二攔位、該第三攔位與該第四攔位其令之二弟 包含 6·如申請專·_ 1項所述的方法， 其中更進一步 大檢查該媒體存取控制位址表内對應到—第三索引值之 -弟五攔位與-第六攔位之儲存空間，當該第三攔位盘 第四棚位.存空間皆填滿相對應之媒體存取㈣位^ 以及 ’ 2該等待儲存之媒體存取控·址填人該第五棚位與 該第/、攔位其中之一，當該第五攔位或該第六搁位其中之 一之儲存空間為淨空狀態； 其中’在該媒體存取控制位址表内，該第三索引值接 籲續該第二索引值之後。 7. —媒體存取控制（MAC)位址管理方法，包含 步驟： 提供一媒體存取控制位址表，包含： 複數連績的欄位，每一欄位儲存一個媒體存取控 制位址；以及 複數連續的索引值，每一索引值對應至少兩個攔 位； 接收一網路封咆，該網路封包包含一媒體存取控制位。 Clienfs Docket No. :VIT-05-0255 TT^ Docket No:0608-A40659TW/fmayYeatsLuo/5/30/2006 18 200803376 址； .址是否已存在於該媒體存取控制位址表;:取控制位 如果該媒體存取控制位址不存在於 址表，則執行一學習步驟，將該媒體押立 該媒體存取控制位址表中，·其中該學習步址紀錄在 根據該媒體存取控制位址運算出—第— 檢查該第-索引值對應的攔位是否仍有空間·’ ，二一索引值對應的攔位皆已填二跑接續 第二索引值所對應的襴位是否仍有空 如果該第二索引值所對應的攔位之-仍有空間，則將 該媒體存取㈣位址寫人财空間賴位。 ' 8·如申明專利㈣第7項所述的媒體存取控制位址管 理方法，其中該媒體存取控制位址表更進一步包含複數時 戳攔位，用以紀錄每_媒體存取控制位址㈣置時間。 9·如申請專利範㈣7項所述的媒體存取控制也址管 理方法，其中該媒體存取控制位址管理方法更進一步包 含，如果該媒體存取控制位址已存在於該嬅體存取控制位 址表，則更新該媒體存取控制位址對應的間置時間。 / 10·如申請專利範圍第7項所述的媒體存取控制位址 管理方法’其中該學習步驟更進一步包含，如果該第一索 引值對應的攔位之一仍有空間，則將該媒體存取抵制位址〃 寫入該有空間的攔位。 Clienfs Docket No.：VIT-〇5-〇255 XT’s Doeket 歸舰 19 200803376 管理^如第7項所述的媒體存取控制位址 g理方法該料步驟更進—步包含， 所對應的攔位皆已填滿，則進行一索引值 =制值覆寫至該第-索引或該第二㈣對應的攔位其Ϊ 址二Li申=範圍第11'貝所述的媒體存取控制位 址,理方法，其中查詢該媒體存取控制位址表的步驟 含檢查該第-索弓丨值及第二㈣值所對應的攔位中，是否 存在該媒體存取控制位址。 —13.如申請專利範圍第7項所述的媒體存取控制位址 管理方法，該學習步驟更進一步包含： 如果該第二索引值所對應的攔位皆已填滿，則檢查接 續該第二索引值的-第三索引值所對應的攔位是否已填 滿；以及 一 如果該第三索引值所對應的攔位之一仍有空間，則將 •該媒體存取控制位址寫入該有空間的攔位。 、 14·如申請專利範圍第13項所述的媒體存、取控制位 址管理方法，其中查詢該媒體存取控制位址表的步驟，包 含檢查該弟一索引值、該弟二索引值以及該第三索引值所 對應的欄位中，是否存在該媒體存取控制位址。 15·如申請專利範圍第7項所述的媒體存取控制位址 管理方法，其中根據該媒體存取控制位址運算出該第一索 引值的步驟’係取該媒體存取控制位址的末七位元，經雜 湊運算而得到該第一索引值。，、 Client’s Docket No. :VIT-05-0255 TT’s Docket No:0008-A40659TW/final/YeatsLuo/5/30/2000 20