기억보단 기록을

Data Link Layer 제어의 기본 기능과 관련 프로토콜에 대해 알아보자.

- Framing

- Flow and Error Control

- Noiseless Channels

- Noisy Channels

- HDLC

- Point to Point

1. Framing

Data Link 계층은 bit들을 프레임(frame)으로 묶어 전송한다.

이러한 frame을 구분할수 있도록 프레임 앞과 뒤에는 일종의 delimiter 를 붙이게 된다.

이러한 framing은 Character-Oriented Framing 과 Bit-Oriented framing 으로 나눌 수 있다.

1) Frame in a Character-Oriented protocol

Frame 에 실려가는 data는 8-bit character로 구성되어있으며, 앞뒤에는 식별자로써 Flag를 붙이게 된다.

이 두 flag 는 각각 start 와 end 를 나타낸다.

- Byte stuffing and unstuffing

Byte stuffing and unstuffing 이란, frame 의 시작과 끝의 혼동을 방지하기 위한 기법이다.

2) Frame in a Bit-Oriented protocol

Bit-Oriented protocol 에서는, 프레임의 시작과 끝을 구분하기 위해 01111110 이라는 특별한 flag를 사용한다.

또한 data에는 임의의 길이를 가진 bit들이 전달될 수 있다.

- Bit stuffing and unstuffing

flog 와의 혼동을 방지하기위하여, 1이 5번 나올경우 뒤에 0 을 임의로 붙여준다.

2. Flow and Error Control

1) Flow contorol

-> Flow contorol 이란 sender 가 receiver가 받을수 있는 데이터의 양을 초과하지 않도록 하는 일련의 데이터 조절 절차이다.

- X-ON/X-OFF : sender 의 전송속도가 receiver의 처리속도 보다 빠를경우, receiver의 buffer에 데이터가 쌓이게 되는데, 일정수준이상을 초과할경우 receiver는 sender 에게 X-OFF 메세지를 전달하게 된다. 또한 buffer에 일정데이터가 처리가 되면 다시 X-ON 메세지를 전달한다.

 - Stop-and-Wait : sender는 먼저 하나의 데이터를 전송하고, receiver로부터 데이터를 처리했다는 메세지인 ACK를 받게된다. ACK를 받은후 다시 데이터를 전송할 수 있다.

- Sliding-Window : sender는 receiver에게 window의 크기만큼의 데이터를 ACK 받는 과정없이 보낼 수 있다.

또한 window크기의 데이터를 보낸후 ACK를 받게되고 다시 window 크기만큼의 데이터를 보낼수 있다.

ACK를 받지 못했을경우 데이터 전송은 자동 중단된다.

2) Error Control

-> 데이터의 전송중 발생하는 오류에 대한 검출 및 복구 과정이다.

- Lost frames : 프레임이 손실되는 경우인데, 이 경우 프레임의 일련번호를 이용해 검출할 수 있다.

- Damaged frames : 프레임이 손상된 경우에는 CRC 혹은 Checksum 등의 방식을 사용해 오류를 검출할 수 있다.

 - Error control Techniques

• Forward error correction : receiver가 직접 오류를 수정하는 방식 ( FEC )
• Backward error correction : receiver는 오류를 검출만 하고, 재전송을 요청하는 방식 ( ARQ )

3) Noiseless Channel

Data Link 의 Protocol 에는 노이즈가 있는 이상적인 채널과 노이즈가 있는 실제 채널이 존재한다.

Noiseless channel 에서는 프레임의 손실, 중복, 손상이 없는 이상적인 채널이다.

이러한 이상적인 프로토콜중 Simplest protocol 과 Stop and Wait Protocol 에 대해 알아보자

- Simplest Protocol

Simplest Protocol 에서는 Error 및 Flow control 의 필요가 없다고 가정하므로 별도의 ACK 등은 고려하지 않는다. 단지 데이터의 전달만을 고려한다.

- Stop and Wait Protocol 

Stop and Wait Protocol  에서는 Flow control 만을 고려한다.

4) Noisy Channels

Noisy Channels 에서는Flow control 의 기능 외에 Error Control 의 기능이 추가된다.

Error control 을 위한 3가지의 ARQ방식을 알아보자.

•  Stop and Wait ARQ
•  Go-Back-N ARQ
•  Selective Repeat ARQ

- ARQ?

ARQ의 동작을 위해서 기본적으로 오류검출 기법이 사용된다. 수신한 프레임의 오류가 없으면, receiver는 positive ack를 보내게 되고 오류가 있다면, negative ack를 보내게 된다. 또한 sender는 positive ack를 time-out내에 받지 못하거나 negative ack를 받을 경우 재전송을 통해 복구하게 된다. 

- Stop and Wait ARQ

하나의 프레임마다 Stop 하고, receiver로부터 ACK 를 수신(Wait)한후 다시 다음 프레임을 전송한다.

sender는 receiver로부터 ack 가 올때까지 전송할 프레임을 버퍼에 보관하게 된다. 또한 ACK의 loss를 대비하기위해 time-out 이 존재한다. 또한 중복된 프레임을 식별하기 위해 프레임마다 번호를 붙이는데. 1bit만을 이용하여 0,1번갈아가며 식별자를 지정한다.

또 sequence number는 다음 프레임  넘버를 지정한다.

구현이 간단하고, 최소의 버퍼크기만을 요구하지만 sender와 receiver간의 오버헤드가 크다.

Data Path 설계

 $Datapath Requirements

- Memory 

- Registers

- PC

- Sign extend

- Add / Sub / Logical Arithmetic

2. ALU (Arithmetic Logic Unit) 설계

우리가 사용할 ALU는 다음과같은 operation 들을 지원해야한다.

- AND OR NOR

- ADD SUB

- SLT

- Carry ( unsigned overflow )

- Overflow detection( signed overflow )

- Zero detection

1) 1bit ALU for AND,OR and ADD

2) 1bit ALU for SUB

Sub 는 Add 를 기반으로 하되 2의 보수를 더해주면 된다.

3) NOR

4)SLT

SLT 는 LSB 의 값 ( 0 or 1) 에 의해서만 result가 결정되므로, 상위 31bit에 대해 0 으로 설정해주고, 

LSB 만 비교하면 된다.

5) Zero detection

Single-Cycle Implementation

앞으로는 Processor 를 구성하는데 사용되는 logic design의 주요 내용을 다시 살펴보고, 이를 기반으로 단일 clock cycle에 단일 instruction을 수행하는 single-cycle processor 를 구현해볼것이다.

순서는 다음과 같다.

1. 설계할 Processor Architecture 선정

2. datapath 설계

3. control 설계

Single cycle processor 에서는 instruction per cycle (CPI) 은 1이며, 

Cycle time 은 동작이 가장 긴 instruction에 의해 결정된다. (성능은 낮다)

Logic Element Review

1) Processor의 logic element 들은 크게 2가지로 구분할 수 있다

- Combinational elements

- State elements

Combinational elements 에서는

output은 current inputs 에 의해서만 결정되고, ALU, mux, decoder, encoder 등이 있다.

또한 일반적으로 feedback path가 존재하지 않는다.

State elements 에서는

state를 저장하는데 사용하고, 일반적으로 clock이 input으로써 사용되고, 특정 조건이 만족할 경우에만 state 

element로 사용되는 control signal 이 존재한다

이러한 Sequential Circuit 은 state element 와 conbinational element 들로 구성되는데,

일반적으로 combinational logic 의 입력은 state element 로부터 오며, output은 current inputs 와 current state에 의해 결정된다. 또한 Feedback path가 허용된다.

2) Clock

clock 은 state elements 가 언제 update 되는지를 결정한다.

따라서 state elements 가 존재하는 sequential logic circuit에서는 반드시 존재하게 된다.

이러한 clock 과 관련해 state element 가 언제 valid 하고 stable 해야하는지를 결정하는것을 clocking methodology 라 하는데, 이에는 Level-sensitive 와 Edge-triggered 두가지 방법이 존재한다.

- Level-sensitive : state change 가 clock 의 특정 level 에서 이루어지고, Latches 또는 Latch로 이루어진 register들이 state elements 로 사용된다.

-  Edge-triggered : state change 가 clock edge 에서 이루어지고 Rising edge 또는 Falling edge 를 사용하게 된다.

Flip-flops 또는 flip-flop 로 이루어진 register들이 state-elements 로 사용된다.

3)

위는 Edge-Trigged Clocking 을 사용한 Sequential Circuit 에서 Setup time 과 Hold time 에 관련된 delay constraints 에 대해 설명한것이다.

먼저 여기나오는 용어에 대해 조금 알아보자면, 

Clock-to-Q : 클락의 엣지가 되서 플립플롭 내에서 D값이 Q로 전달되는 delay 이다. 

Setup time : state elements 로의 입력은 클락 엣지에서 setup time 전부터는 valid 해야한다는 것을 의미한다.

Hold time : state elements 로의 입력 클락엣지 이후에도 hold time 동안 valid 해야한다.

Longest path delay : state elements 사이의 최대 delay

4)Feedback Path

Sequential circuit 에서는 위와같이 feedback 이 허용된다. 또한 위와 같은 회로에서는 reset 또는 preset logic 이 필요하다. Feedback path 가 있더라도 clock을 사용해 feedback을 일정시간 막아줌으로써, 동일시간의 즉각적인 feedback 이 없으므로 circuit의 안정성이 유지된다.

반대로 combinational circuit에서는 즉각적인 feedback 으로 값이 안정되지 않는다. 

5) Signal 관련 용어

- Control signal : Multiplexer 에서 입력을 선택하거나 functional unit 의 동작을 지시하는데 사용되는 signal

- Data signal : Functional unit 에 의해 처리되는 정보를 담고있는 signal

- Bus : 단일 logic signal로 취급되는 signal line 들의 묶음

- Asserted : Signal 이 logically high(active) 인 상태 또는 그 상태로 변하는것

- Deasserted : Signal 이 logically low(inactive) 인 상태 또는 그 상태로 변하는것

6) Mux 

여러 input들 중 Control signal 에 따라 1개를 output 으로 내보냄, Selector 라고도 함.

32bit wide multiplexer 는 실제로는 32 개의 1-bit multiplexer 들로 이루어진 array이다.

이와같은 logic element 의 array는 다양한 logic element 들에 적용되 수 있다.

ex) latch 또는 flip flop 등의 array 가 register를 구성한다.

7) Latch

Latch 는 Clock 이 asserted 되어있는 동안 input이 변할때마다 state 가 변경된다. (Level sensitive, Active high 또는 Active low)

D-latch : Clock 이 asserted 되어있는 동안에 input signal의 값을 내부 state 에 저장하는 latch. ( 특정조건이 만족할경우에만 state change 가 일어난다면, write enable 로 사용되는 control signals 가 존재한다.)

8) Flip - Flop

내부 저장된 state 를 output 으로 내보내는 state element

Clock edge 에서만 state change가 이루어진다. (Edge - sensitive) 

9) Register

Edge triggered clocking methodology 를 사용하기위해 D flip flop으로 만들어진 register들을 사용한다.

n - bit register란 n bit의 input 과 n bit의 output를 가지게 된다.

clock signal 은 input value 가 register에 언제 write되는지를 결정한다.

여기서 clock 위의 삼각형 표시는 flip flop 의 사용 의미를, 동그라미 표시는 falling edge 사용 표시이다.

10) Register File

Register 가 flip flop들의 array라고 한다면, Register file은 register의 array이다.

MIPS 의 경우 32개의 register 를 가지고있고, register number 를 지정하여 특정 register 값을 read 하거나 write 를 할 수 있다.

여기서 사용할 register file 은 두개의 read port 와 하나의 write port를 사용할 것이다.

가령 R-format instruction 의 경우, 각 instruction 에 대해 2개의 register operand 를 read 하고 1개의 data 를 register file 에 write 해야한다. 따라서 Input 과 Output의 관점에서는, one data input 과 two data ooutput을 갖는다.

이때 write enable 값이 존재하는데, 가령 add 연산의 경우 register write를 하지만, sw 혹은 beq 연산의 경우 write 과정은 따로 필요없기 때문이다.

이 때, Read operation 은 enable 또는 clock signal 과 관련없이 read 되고 Ra Rb 에 의해 지정된 register 값을 BusA 와 BusB 를통해 출력하게 된다. Write operation 은 RegWrite 의 값( 0 or 1) 에 따라 BusW를 통해 write 한다.

11) Memory

위는 단순화를 위해 사용한 ideal 한 memory 의 형태이다.

메모리에서도 마찬가지로 memwrite 와 memread 의 값에따라 read write 를 수행하게 된다.

여기서 read enable 을 굳이해야하는것에 관해선 메모리의 값을 건드리는것 아니기때문에 항상 read 해도 되지만,

Invalid address 의 경우 read 하더라도 문제를 발생하기때문에 필요하다..!

ㄴㄴ

1. Data Communication

컴퓨터공학에선 'Data' 를 관찰하고 측정해 얻은 Information을 가공해 얻은것으로 정의한다.

컴퓨터 및 디바이스 들은 어떠한 방식으로 이러한 data를 전송하고 교환하는지에대한 지식을 다루는 포스팅이 될것같다. 모든 포스팅은 전자공학부 조유제교수님의 데이터통신수업을 참고로 작성한다.

2. Components of Data Communication

데이터 통신에서는 이러한것들을 기본적인 구성요소로 두고있다..

이러한 데이터, 즉 Message는 문자 text가 될수도, 숫자가될수도, 혹은 그림, 영상, 오디오등의 미디어들이 될수도있다.

하지만 당연하게도 컴퓨터는 0과1, 즉 전압의 on off를 통한 기계다. 따라서 문자혹은 숫자는 0과1 흔히생각하는 아스키코드등으로 번역되어 표현할 수 있다. 하지만 오디오 혹은 비디오는 continuous한 아날로그 시스템들이다.

이러한 아날로그를 0과1의 디지털표현으로 바꾸어 전달하는것도 Data Communication으로 해결해야할 과제인것이다.

3. Network

위에서 말한 데이터들은 디바이스 서로간에 네트워크를 통해 전송이된다.

흔히 쓰는 용어지만, 이러한 Network라는 용어도 추후다룰 Network Model 적인측면에서 Layer에대한 이해가있어야

완벽히 이해할 수 있다.

단순히 device connection측면에서만 살펴보면 다양한 연결형태를 띄는데, mesh, star,bus 그리고 ring 형태가 있다.

4. Categories of Network

네트워크에도 디바이스를 연결하는 범위에 따라 Local Area Network, Wide Area Network, Metropolitan Area Network 등으로 구분된다.

Local Area Network, 즉 LAN 은 사무실, 빌딩정도의 네트워크이다. 인터넷선을 랜선이라고부르는것이 떠오르는가.

과거에는 Bus형태의 Topology를 사용했지만 현재는 Star Topology를 대체로 사용한다.

Wide Area Network, 즉 WAN 은 한마디로 넓은 범위의 네트워크이다. 하나의 나라, 대륙을 커버하는정도의 영역을 가진

다. 따라서 지역적으로 연결된 LAN들을 서로 이어주는 개념이며, 호스트끼리가 아닌 switch 혹은 라우터, 모뎀들 사이를 연결한다. 또한 개인사용자가 아닌, 국가에 통신사업자 등록을한, 예를들어 KT , SKT 같은 사업자들이 구축한다.

5. Inter Network