TWI324471B - Mac address management method - Google Patents

Description

1324471 九、發明說明： » 【發明所屬之技術領域】 本發明係有關於電腦網路’尤其是有關於媒體存取控 制位址（Media Access Control Address，MAC Address)管 理方法。 _ 【先前技術】 . 第la圖係為習知的媒體存取控制位址表(Media Access _ Control Table, MAC Table)。一般的網路裝置例如路由器或 交換器中，都會提供一塊記憶體以將所蒐集之媒體存取控 制位址（Media Access Control Address，MAC Address)記 。錄至此記憶體上並建立一媒體存取控制位址表，若網路上 存在某些未被記錄之媒體存取控制位址，則能透過學習的 方式更新媒體存取控制位址表以記錄所有網路上所識別到 的媒體存取控制位址。如圖所示’媒體存取控制位址表可 以方便地官理與查詢所學習到的媒體存取控制位址，其 # 中，媒體存取控制位址表包含複數連續的欄位，如第一攔 位100、第二欄位102、第三攔位1〇4與第四欄位1〇6 等等.....’每—欄位皆能儲存-個媒體存取控制位址。此 媒體存取控制位址表中另紀錄了每四個搁位的記憶體位址 以當成索引值，如Indexl為第一攔位1〇〇、第二欄位 K>2、第三棚位HM與第四攔位1〇6之索引值。所以藉由 索引值，可以快速檢索與存取媒體存取控制位址。 第lb圖係為習知的媒體存取控制位址管理方法流程 圖。若-塊記憶體被規劃成包含2〇48個樹立，則此記憶體

Client’s Docket N〇.:VIT-05-0255 TT's Docket No：0608-A40659TW/fmalAreatsLuo/5/3〇/2〇〇6 6 、，一有512個索引值，且每一索引值皆對應至四個攔位。 所以在步驟SU)2中’當接收—個封包時將此封包之媒體 存取控制位址經過—個雜凑運算（HASH) 體存取控制位址所屬的索弓丨值。另外，索引值的產生，也 可^是從祕體麵㈣位址中取末九錄元直接產生。 接著’在步驟SUM中’查詢此記憶體之媒體存取控制位址 表以t清在步驟請2中所得之索引值所對應的四個攔位 中是否已經存在此媒體存取控制位址。如果不存在，則 進行步驟S108 ’透過一學習步驟，將此媒體存取控制位址 紀錄至此記憶體中以更新媒體存取控制位址表。然而，一 般來說’此媒體存取控制位址表中的每個媒體存取控制位 址：有-個逾時期限。如果某一個媒體存取控制位址超過 -疋的日相未有存取的動作，則朗體存取控制位址表從 對應的欄位除該媒H存取控制位址。所以在步驟S⑽ 的檢查結果巾’如果查到該媒體存取控制位址已經存在於 此媒體存取控制位址表中’則進行步驟S1G6，只要更新此 媒體存取控制位址所對應的存取時間，使此媒體存取控制 位址保持在逾時期限之内。 第2a圖係為習知的媒體存取控制學習步驟的流程圖。 此學習步驟如下所述。首先，在步驟S2G2中，根據此媒體 存取控制位址所產生的索引值去搜尋此媒體存取控制位址 表中對應的四個欄位。在步驟S204中，逐一判斷此四個欄 位中是否有空間可供存放此媒體存取控制位址。如果其中 一個攔位是有空間的，則進行步驟S2〇6，將此媒體存取控

Client's Docket No.:VIT-05-0255 TTs Docket No:0608-A40659TW/final/YeatsLuo/5/30/2006 7 1324471 制位址存放至有空間的攔位。如果四個攔位都已被佔滿， 則進行步驟S208 ’將此媒體存取控制位址覆寫至此四個攔 位其令之-。覆寫的原則，可以選擇最接近逾時期限的搁 位，也可以是四個攔位依序輪流，或是隨機犧牲此四個攔 位其中之一。 第2b圖係為習知的媒體存取控制位址表。圖上顯示索 引Index 1、Index2和Index3，各對應四個攔位。其中Index i 的四個欄位為第一欄位200、第二攔位202、第三欄位 204與第四欄位206，且第一攔位200已儲存了媒體存取 控制位址（標示為learned)，而其他三個攔位是空的（標 示為empty)。索引Index2的四個攔位為第五攔位2〇8、 第六欄位210、第七欄位212與第八欄位214且先前均 已填滿了媒體存取控制位址（learned )，當有對應至index2 之一新的媒體存取控制位址要填入時，第五欄位2〇8就被 覆寫了（標示為overwrite)。而索引Index3所對應的四個 攔位為第九攔位216、第十欄位218、第Η--攔位220與 第十二攔位222，則全部都是空的。 雖然利用索引值可以很方便的檢索或存取四個或多個 相對應的媒體存取控制位址。然而這樣的媒體存取控制位 址管理方法’卻有技術上的缺點。在本例中可見，當In(jex2 的四個攔位都填滿時，若是再出現屬於Index2的媒體存取 控制位址’就必須進行覆寫，拋棄Index2的其中一欄位裏 的既有值。而事實上記憶體中還有很多空間沒有利用，例 如Index3的攔位仍有空間閒置。因此在記憶體還沒有充份

Client’s Docket N〇.:VIT-05-0255 TT*s Docket No:0608-A40659TW/final/YeatsLuo/5/30/2006 1324471 • 利用的情況下卻必須拋棄某些媒體存取控制位址是很不合 理的做法’導致無法有效利用資源。 【發明内容】 本發明提供一種一媒體存取控制位址（Media Access Control Address，MAC Address)管理方法。此方法包含下 列步驟。首先’檢查一媒體存取控制位址表（MAC table)内 對應到一第一索引值之一第一攔位與一第二攔位之儲存空 鲁間；接著，當此第一欄位與此第二欄位之儲存空間皆填滿 相對應之媒體存取控制位址’檢查此媒體存取控制位址表 内對應到一第二索引值之一第三欄位與一第四欄位之儲存 w 空間；最後，當此第三攔位或此第四欄位其中之一之儲存 空間為淨空狀態，將一等待儲存之媒體存取控制位址填入 此第二攔位與此第四欄位其中之一，其中，在此媒體存取 控制位址表内’此第二索引值接續此第一索引值之後。 本發明提供一種媒體存取控制位址管理方法，在某個 • 索引值所對應的攔位用完時，還能借用下一索引值的欄位 來儲存媒體存取控制位址，大大的增加了空間攔位的利用 率。首先，提供一媒體存取控制位址表，包含複數連續的 欄位，母一欄位儲存一個媒體存取控制位址。其中的每一 索引值對應至少兩個攔位。當接收一網路封包時，查詢此 媒體存取控制位址表，判斷此網路封包中的媒體存取控制 位址是否已存在於此媒體存取控制位址表中。如果此媒體 存取控制位址不存在於此媒體存取控制位址表，則執行一 學習步驟，將此媒體存取控制位址紀錄在此媒體存取控制

Client's Docket N〇.：VIT-05-0255 TT's Docket N〇:0608-A40659TW/finalAfeatsLuo/5/30/2006 1324471 位址表中。 此學習步驟包含下列步驟。首先根據此媒體存取控制 位址運算出一第一索引值，接著檢查此第一索引值對應的 欄位是否仍有空間。如果此第一索引值對應的欄位皆已填 滿，則檢查接續此第一索引值的一第二索引值所對應的攔 位是否仍有空間。如果此第二索引值所對應的攔位之一仍 有空間，則將此媒體存取控制位址寫入此有空間的欄位。 _ 此媒體存取控制位址表尚包含複數時戳攔位，可用來 紀錄每一媒體存取控制位址的閒置時間。在判斷此網路封 包中的媒體存取控制位址是否已存在於此媒體存取控制位 址表的過程中，如果此媒體存取控制位址已存在於此媒體 存取控制位址表，則更新此媒體存取控制位址對應的閒置 時間。 更進一步的，如果此第二索引值所對應的襴位皆已填 滿，則進行一覆寫步驟，將此媒體存取控制值覆寫至此第 • 一索引或此第二索引對應的攔位其中之一。先前查詢此媒 體存取控制位址表的步驟，係檢查此第一索引值及第二索 引值所對應的攔位中，是否存在此媒體存取控制位址。' 更進-步的，如果此第二索引值所對應的搁位皆已填 滿’則檢查接續此第二索引值的一第三索引值所對應的棚 位是否已填滿。如果此第三索引值所對應的攔位之一仍有 空間’則將此媒體存取控制位址寫入此有空間的攔位。而 先則查5旬此媒體存取控制位址表的步驟，即為檢杳此第 索引值、此第二索引值以及此第三㈣值所對應的爛位

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

Client's Docket N〇.:VIT-05-0255 TT5s Docket No:0608-A40659TW/fmal/YeatsLuo/5/30/2006 另外，若此第五欄位與丄 相對應之媒體存取控制位址/、欄位之錯存空間皆填滿 覆寫步驟，亦即將此等待錯存=二驟S39巾’進行-此第-欄位、此第二欄位=體存取控制位址覆寫至 位與此第六欄位欄位其中之一 一位、此第四此第五攔 之每-攔位均標示代表逾時媒體存取控制位址表 取控制位址的閒置時間 2 紀錄每-媒體存 寫最接近逾時期限的搁位方式’可以是選擇覆 犧牲此些襴位其中之一。°以疋依序輪流，或是隨機 若在步驟S30中，此第一 之儲存㈣為淨空狀態時，則=第二攔位其中之一 待儲存之媒體存取控制位址填入此第^斤不，將此此等 其中之一。若在步驟S32中，、此第攔位與此第二攔位 φ ^ ^ . ^ a . 此第二欄位或此第四欄位其 此料德力子工^為淨空狀態時，則如步驟S38所示，將 等=存之媒體存取控制位址填入此第三搁位與此第四 攔位其中之一。 此外，如果《ϋ麵㈣位址已存在於此媒體存取 工制位址纟，則更新此媒體存取控制位址對應的閒置時間 即可。 第3b圖係為本發明的另一媒體存取控制學習方法流 程圖本發明供的媒體存取控制位址管理方法，可以在 某個索引值所對應的攔位用完時，借用下一索引值的欄位 來儲存媒體存取控制位址，大大的增加了空間欄位的利用 率。在步驟S302中，根據此媒體存取控制值產生的索引值

Client's Docket N〇.:VIT-05-0255 TT's Docket No:0608-A40659TW/fmalAreatsLuo/5/30/2006 12 1324471 去搜哥此媒體存取控制位址表中對應的複數棚位。在本實 施例中，每個索引值可以是只對應兩個搁位，也可以是四 個或六個襴位。接著在步驟S304中，逐一判斷此些搁位是 否有空間可存放此媒體存取控制位址。如果此些搁㈣中 -個是有空間的，則進行步驟S3G6，將此媒體存取控制位 址寫入此攔位。相對的，如果此索弓i值所對應的所有棚位 皆沒有空間了，則跳至步驟s扇，搜尋下—索引值的搁 位’逐-判斷此些欄位是否有空間可存放此媒體存取控制 位址。同樣的，如果此些攔位其中—個是有空間的，則進 行步驟剛，將此媒體存取控制位址寫入此搁位。如果步 驟S308中已經沒有空間了，則跳至步驟sM2，進行一覆 寫程序。在覆寫程序中，此媒體存取控制位址可以被寫入 步驟隨所檢查過的欄位其中之一，至於要如何選擇取代 哪-個欄位’則可以是依照各種不㈣原則㈣。例如， 了以選擇最接近逾時期限的欄位，也可以是依序輪流，或 是隨機犧牲此些欄位其中之一。更逸一 更進步的，此覆寫程序 也可以選擇步驟S308所檢查過的欄位做為犧牲取代的對 象。在本流程圖中’僅介紹了借用下一索弓丨值的搁位，作 不限定於此。舉例來說’如果步驟s 3 〇 8中檢查出沒有空間 了’也可以更進一步借用再下一個索引值的欄位叹重二 行檢查與寫入的步驟。 =4 γ為本發明實_之—的媒體存取控制位址 表。母-個索引值對應兩個欄位，而每個欄 戳值（依時間順序表示為T卜T2,……、± 時 )°時戳值記錄著

Client's Docket N〇.:VIT-05-0255 TT s Docket No:0608-A40659TW/final/YeatsLuo/5/3〇/2〇〇6 13 1324471 每一欄位的更新時間，可以用來計算閒置時間，做為逾期 汰舊順序的判斷依據。時戳管理已有許多習知的做法，在 本實施例中不加詳述。在第4圖中，Indexl的攔位為第一 欄位400與第二欄位402，且第一欄位400已填滿 (learned )而第二攔位402則是空的。如果一個屬於 Index2的媒體存取控制位址進來時，發現Index2的第三欄 位404與第四攔位406皆已填滿，則借用Index3的第五 攔位408來存放（標示為learned(2))。如果Index3的第 五欄位408與第六攔位410也存滿了，則進行覆寫，例 如寫回Index2的第三欄位404中（標示為overwrite(2))。 每個索引值皆可向下一個索引值借攔位，因此可看到， Index3向Index4借了兩個攔位，而Index4向Index5借了 一個攔位。因為每一媒體存取控制值可能存放的範圍被擴 充了，所以大大的善用了可能閒置的空間。此外，也因為 每一媒體存取控制值可能存放的範圍跨越了不同的索引 值，所以在第lb圖中提及的步驟S104，查詢媒體存取控 制位址表的方式’也要對應的改良。基本上索引值和攔位 的記憶體位址有對應關係，在記憶體中都是連續的，所以 在進行步驟S104的查詢時’就是把逐欄比對的步驟延續至 下一個索引值，依此類推。 第5圖係為本發明另一實施例的媒體存取控制位址表 示意圖。對於索引值Index A而言，媒體存取控制位址可以 借用到下兩個索引值，即IndexC。因此可能存放indexA 對應的媒體存取控制值的欄位標示為A。同理，可能存放

Client's Docket N〇.:VIT-05-0255 TT's Docket No:0608-A40659TW/finalAreatsLuo/5/30/2006 14 1324471

IndexB對應的媒體存取控制值的欄位標示為B。因此在 IndexC對應賴財’可能存放的雜麵㈣位址就包 含了 A ’ B和C三種。同樣的，這種媒體存取控制位址表 對應的查詢方式也會需要些許對應的調整。舉例來說，A 可能存放在IndexA、IndexB和IndexC所對應的所有棚位 中，所以為了查詢A，就必須搜遍IndexA、IndexB和 所對應的所有攔位。在本實施财每個索引值對應兩個棚 位。但也可以是其他的數目，並不限定於此。索引值的產 生，可以是取此媒體存取控制位址的末十位元直接當成索 引，或是將此媒體存取控制位址經雜凑運算轉換 ^ 位元的數值。 、双一個十 【圖式簡單說明】 第la圖係為習知的媒體存取控制位址表； 第lb圖係為習知的媒體存取控制管理方法汸程. 第2a圖係為習知的媒體存取控制學習方法漭^圖 第2b圖係為習知的另一媒體存取控制位址表· 第3a圖係為本發明的媒體存取控制學習方法节程·. 第3b圖係為本發明的另一媒體存取控制學流 程圖； •第4目係為本發明實施例之一的媒體存取控制位址 表；以及 第5圖係為本發明另一實施例的媒體存取控制位址表 不意圖® 【主要元件符號說明】

Client's Docket N〇.：VIT-05-0255 TT's Docket No:0608-A40659TW/fmal/YeatsLuo/5/30/2006 15 1324471 100、102、104、106〜屬於Indexl之第一欄位、第二欄位、 第三欄位與第四欄位 108、110、112、114〜屬於Index2之第五欄位、第六欄位、 第七欄位與第八欄位 116、118、120、122〜屬於Index3之第九欄位、第十欄位、 第十一攔位與第十二欄位 200、202、204、206〜屬於Indexl之第一欄位、第二欄位、 第三棚位與第四搁位 208、210、212、214〜屬於111(16\2之第五欄位、第六攔位、 第七欄位與第八欄位 216、218、220、222〜屬於Index3之第九欄位、第十攔位、 第十一欄位與第十二欄位 400、402〜屬於Indexl之第一欄位與第二欄位 404、406〜屬於Index2之第三攔位與第四欄位 408、410〜屬於Index3之第五欄位與第六欄位 412、414〜屬於111(16乂4之第七攔位與第八攔位 416、418〜屬於Index5之第九攔位與第十欄位 16

Client’s Docket N〇_:VIT-05-0255 TT's Docket No:0608-A40659TW/finalA"eatsLuo/5/30/2006

Claims (1)

1324471 % 案號095Π9379 98年7月20日 修正本 年月日修正本 十、申請專利範圍： 1.一媒體存取控制位址 （Media Access Control Address，MAC Address)管理方法，包含下列步驟： 檢查一媒體存取控制位址表（Media Access Control Table，MAC Table)内對應到一第一索引值之一第一欄位與 一第二攔位之儲存空間； 當該第一攔位與該第二襴位之儲存空間皆填滿相對應 之媒體存取控制位址，檢查該媒體存取控制位址表内對應 籲到一第一索引值之一第三攔位與一第四攔位之儲存空間； 以及 當該第三欄位或該第四攔位其中之一之儲存空間為淨 空狀態，將一等待儲存之媒體存取控制位址填入該第三 位與該第四欄位其中之一； 〃 一 該第二索引值接 其中，在該媒體存取控制位址表内 續該第一索引值之後。

2. 如申請專職㈣丨項所述的方法，其中該媒體存 取控制位址表更進-步包含複數時戮欄位，用 、—一 媒體存取控制位址的閒置時間。 、、’ ’录母一 3. 如申請專利關第丨項所述的方法， 包含，如果該媒體存取控制位址已存 媒 位址表，敎新該髓存取㈣位 ^^取控制 4如申往直剎梦閉哲 了應的閒置時間。 4·如U利㈣第丨項所述的方法， 包含，將該等待儲存之·存取㈣位址進一步 與該第二糊位其中之-’當該第-櫚位或該第 VIT-05-0255/0608-A40659TW/finall 17 1324471 9 之一之儲存空間為淨空狀態。 5. 如申請專利範圍第1項所述的方法，其中更進一步 '包含，如果該第三欄位與該第四攔位皆已填滿，則進行一 覆寫步驟，將該等待儲存之媒體存取控制位址覆寫至該第 一欄位、該第二欄位、該第三攔位與該第四攔位其中之一。 6. 如申請專利範圍第1項所述的方法，其中更進一步 包含： 檢查該媒體存取控制位址表内對應到一第三索引值之 # 一第五欄位與一第六欄位之儲存空間，當該第三欄位與該 第四欄位之儲存空間皆填滿相對應之媒體存取控制位址； 以及 將該等待儲存之媒體存取控制位址填入該第五欄位與 該第六襴位其中之一，當該第五攔位或該第六欄位其中之 一之儲存空間為淨空狀態； 其中，在該媒體存取控制位址表内，該第三索引值接 續該第二索引值之後。 _ 7. —媒體存取控制（MAC)位址管理方法，包含下列 步驟： 提供一媒體存取控制位址表，包含： 複數連續的欄位，每一欄位儲存一個媒體存取控 制位址；以及 複數連續的索引值，每一索引值對應至少兩個襴 位； 接收一網路封包，該網路封包包含一媒體存取控制位 VIT-05-0255/0608-A40659TW/fmall 18 1324471

址； 查詢該媒體存取控制位址表，判斷該媒體存取控制位 址是否已存在於該媒體存取控制位址表中；以及 如果該媒體存取控制位址不存在於該媒體存取控制位 址表，則執行一學習步驟，將該媒體存取控制位址紀錄在 該媒體存取控制位址表中；其中該學習步驟包含： 根據該媒體存取控制位址運算出一第一索引值； 檢查該第一索引值對應的攔位是否仍有空間； • 如果該第一索引值對應的攔位皆已填滿，則檢查接續 該第一索引值的一第二索引值所對應的攔位是否仍有空 間；以及 如果該第二索引值所對應的欄位之一仍有空間，則將 該媒體存取控制位址寫入該有空間的攔位。 8.如申請專利範圍第7項所述的媒體存取控制位址管 理方法，其中該媒體存取控制位址表更進一步包含複數時 戳攔位，用以紀錄每一媒體存取控制位址的閒置時間。 • 9.如申請專利範圍第7項所述的媒體存取控制位址管 理方法，其中該媒體存取控制位址管理方法更進一步包 含，如果該媒體存取控制位址已存在於該媒體存取控制位 址表，則更新該媒體存取控制位址對應的閒置時間。 10.如申請專利範圍第7項所述的媒體存取控制位址 管理方法，其中該學習步驟更進一步包含，如果該第一索 引值對應的欄位之一仍有空間，則將該媒體存取控制位址 寫入該有空間的欄位。 VIT-05-0255/0608-A40659TW/finall 19 1324471 11. 如申請專利範圍第7項所述的媒體存取控制位址 管理方法，該學習步驟更進一步包含，如果該第二索引值 所對應的攔位皆已填滿，則進行一覆寫步驟，將該媒體存 取控制位址覆寫至該第一索引或該第二索引對應的欄位其 中之一。 12. 如申請專利範圍第11項所述的媒體存取控制位 址管理方法，其中查詢該媒體存取控制位址表的步驟，包 含檢查該第一索引值及第二索引值所對應的攔位中，是否 存在該媒體存取控制位址。 13. 如申請專利範圍第7項所述的媒體存取控制位址 管理方法，該學習步驟更進一步包含： 如果該第二索引值所對應的欄位皆已填滿，則檢查接 續該第二索引值的一第三索引值所對應的攔位是否已填 滿；以及 如果該第三索引值所對應的欄位之一仍有空間，則將 該媒體存取控制位址寫入該有空間的攔位。 14. 如申請專利範圍第13項所述的媒體存取控制位 址管理方法，其中查詢該媒體存取控制位址表的步驟，包 含檢查該第一索引值、該第二索引值以及該第三索引值所 對應的欄位中，是否存在該媒體存取控制位址。 15. 如申請專利範圍第7項所述的媒體存取控制位址 管理方法，其中根據該媒體存取控制位址運算出該第一索 引值的步驟，係取該媒體存取控制位址的末十位元，經雜 湊運算而得到該第一索引值。 VIT-05.0255/0608-A40659TW/fmall 20