I
II BoyerMoore Robin Karp AB
III
IV
V
VI
VII L
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 PMA CSMA/CD MDI AUI PLS MAC LLC MAU
22
23
24
25
圖 2-5 2.1.3 CRC-32 硬體線路圖 CSMA/CD 通訊協定 CSMA/CD 通訊協定的運作可以在不同的傳輸媒介上 如同軸電 纜 無遮蔽式雙絞線 或光纖 初期制定 CSMA/CD 網路相關規格時是 在同軸電纜上定義的 為了方便起見 以下使用同軸電纜的網路環境 來說明此通訊協定的運作原理如下 流程圖請參考圖 2-6 與圖 2-7 步驟 1 每一個工作站在傳送之前必須先監聽同軸電纜上是否已 經有訊號在傳送(Carrier Sense) 如果沒有則可立刻將訊框傳送出 去 如果有則表示其他工作站正在傳送 此時工作站繼續監聽同軸電 纜上的訊號 直到訊號消失 該訊框傳送完畢 後立刻將其訊框傳送 上電纜 步驟 2 在傳送訊框同時也要繼續監聽同軸電纜上的訊號 看看 是否發生衝撞 如果發生衝撞則立即停止傳送訊框並且改傳送一個 擾 亂訊號 (Jamming Signal) 強迫造成更嚴重的衝撞 使得每一個參 與衝撞的工作站能確實偵測出衝撞 否則表示該筆訊框成功的傳送出 26
Receive Frame Set carrier sense signal ON Acquire bit synchronization Preamble of frame Start of frame? NO YES Receive data SFD of frame (data=11) YES Collision detected? NO NO Address matches : Promiscuous mode Local address Multicast address Broadcast address Receive finished? YES Destination address matched? NO YES NO CRC correct? YES Compare FCS of frame by CRC checker Increment Error Count NO Length field correct? YES Length>=64 bytes Length<=1518 bytes Strip Preamble,SFD,FCS of frame Reject frame Receive successful! Discard frame 27
Transmit Frame Assemble a packet from the Frame and Set Attempt Counter to zero NO Is another node transmitting? YES Other transmission finished? NO Transmit 32 bits of jam sequence Increment attempts YES Has IPG passed since last transmission? YES NO Delay rest of IPG time YES Attempts>16? Transmit first bit of the packet Delay entire of IPG time NO Compute backoff time Collision detected? Transmit next bit of the packet NO YES Delay backoff time Transmission finished? NO YES Transmission Failed! Too many Collision! Transmission successful! 28
29
30
圖 2-8 基頻 CSMA/CD 網路衝撞偵測 31
Collision Detect Carrier Sense Collision Recovery, IFG Timing Protocol PLA Handshake MAC Unit DMAC SMAC Bus Arbitration / Handshake NIC s DMA Local Remote DMA DMA BREQ, IRQ Local Address Remote Address Internal BUS Receive Clock Receive Data (serial data) Receive Deserializer Receive/ Tansmit FIFO Handshake Buffer Ring Receive Buffer To Host Memory Transmit Clock Transmit Buffer Transmit Data M U X Tansmit Serializer CRC Generator / Checker M U X Preamble/ Synch / JAM pattern Gen. 32
33
34
35
36
37
38
39
40
41
Filter chains NIC 1 NIC 2 NIC 3 Controller : 42
43
44
45
46
47
48
49 PREROUTING POSTROUTING OUTPUT OUTPUT PREROUTING OUTPUT INPUT FORWARD Filter table Iptables Mangle table Nat table
50
51 2? 1 4? 5 3
PREROUT Routing Decision FORWARD POSTROUTING INPUT OUTPUT 52
INPUT chain Rule 1: -p ICMP j DROP Rule 2: -p TCP j test Test chain Rule 1:-s 140.134.30.1 Rule 2:-d 140.134.30.1 Rule 3: -p UDP j DROP 53
54
55
56
57
58
59
60
61
62
63
64
65
( O(M+N) G-bit/s VHDL (4.2 ) 4-1 O(N/S+M)S bit S text string pattern ( bits pattern bits ) VLSI c-mos 66
( text string pattern 1 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0..... 1 1 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 0 4-2 i text string a b c x y z a b c d a b c i d a b x y k pattern a b c d a b x y next [j] j next [j] 4-3 text string pattern a b c x y z a b c d a b c i d a b x y k a b c d a b x y next [j] 4-4 67
I j I j next [j] j pattern 4.1.3 BoyerMoore pattern pattern skip[ ] text string xskip[x] pattern x text string pattern pattern skip[x] text string WHICH-FINALLY-HLATS-AT-THAT pattern AT-THATY 4-5 ~ 4-1.9 i text string WHICH-FINALLY-HLATS-AT-THAT pattern M AT-THAT j 4-5 i j pattern i pattern skip[f]7 text string WHICH-FINALLY-HLATS-AT-THAT pattern M AT-THAT i j 4-6 i - j T j i j skip[-]4 i 4 (skip[-]4) j pattern text string WHICH-FINALLY-HLAT S-AT-THAT pattern M AT-THAT i j 4-7 i L j j i j i (mj1) skip[s]7 68
i text string WHICH-FINALLY-HLATS-AT-THAT pattern M AT-THAT j 4-8 jpattern 4 ij - skip[-] 4 i 4 j pattern i text string WHICH-FINALLY-HLATS-AT-THAT pattern M AT-THAT j 4-9 i j j i pattern text string WHICH-FINALLY-HLATS-AT-THAT pattern M AT-THAT j (ij ) 4-10 i 4.1.4 Robin Karp (encode) text string a b c e a b e a b c d 2 26 1 0 26 26 2 1 0 26 26 26 2 1 26 26 2-1 26 ) 26+5 M 1 d d 69
4.2.1 VHDL (Pipelining) 4-11 A B C E F G H A 1 1 1 1 1 1 1 1 A 1 0 0 0 0 0 0 1 1 (pattern) (pipelining) clock buffer1buffer2 text string enable clock buffer1 buffer2 buffer2 enable A B C E F G H A B C D E F G A B E F A B G H I J E F G H D M F K B A D C E G H F C D E F A C F G 70
A B C E F G H A 1 1 1 1 1 1 1 1 A 1 0 0 0 0 0 0 1 1 B C D 71
A B C E F G H A 1 1 1 1 1 1 1 1 A 1 0 0 0 0 0 0 1 1 B 0 1 0 0 0 0 0 0 B C D 72
B C D E F G A B 1 1 1 1 1 1 1 1 A 0 0 0 0 0 0 1 0 0 C 0 1 0 0 0 0 0 0 B C D 73
B C D E F G A B 1 1 1 1 1 1 1 1 A 0 0 0 0 0 0 1 0 0 DC 1 1 0 0 0 0 0 1 B 0 0 1 0 0 0 0 0 C D 74
E F A B G H I J 1 1 1 1 1 1 1 1 A 0 0 1 0 0 0 0 0 0 D 1 1 0 0 0 0 0 1 B 0 0 1 0 0 0 0 0 C D 75
E F A B G H I J 1 1 1 1 1 1 1 1 A 0 0 1 0 0 0 0 0 0 AD 1 1 0 0 0 0 0 1 B 0 1 0 0 0 0 0 0 C 0 0 0 1 0 0 0 0 D 76
E F G H D M F K 1 1 1 1 1 1 1 1 A 0 0 0 0 0 0 0 0 0 A 1 0 0 0 0 0 0 1 B 0 1 0 0 0 0 0 0 C 0 0 0 1 0 0 0 0 D 77
E F G H D M F K 1 1 1 1 1 1 1 1 A 0 0 1 0 0 0 1 0 0 E GA 1 1 0 0 0 0 0 1 B 1 1 0 0 0 0 0 0 C 0 0 1 1 0 0 0 0 D 78
B A D C E G H F 1 1 1 1 1 1 1 1 A 0 1 0 0 0 0 0 0 0 E G 0 0 0 0 0 0 0 1 B 1 0 0 0 0 0 0 0 C 0 0 1 0 0 0 0 0 D 79
4.2.2 (AB) pattern enable 1( A ) enable 1 compare 1 ( 1) B C D E F G A B 1 1 1 1 1 1 1 1 A 0 0 0 0 0 0 1 0 0 B 0 1 0 0 0 1 0 0 C D 80
4.2.3 (AB) pattern enable 1( A ) enable 1 compare 1 clock compare 1 B ( ) B C D E F G A B 1 1 1 1 1 1 1 1 A 0 0 0 0 0 0 1 0 0 C 0 0 0 0 1 0 0 0 B 81
82
83
84
85
86
87
88
VHDL 90
90