(Chap12) Ethernet(IEEE 802.3)

Goal of MAC : Increasing throughput (link efficiency) and reducing latency by decreasing collisions.

Random access (content based) MAC:

• (pure/slotted) ALOHA : no carrier sensing, no collision detection by carrier sensing, collision detection/resolution using ACK frame in the MAC sub layer, back-off time = random
• (non-/1-/p-) persistent CSMA : no collision detection by carrier sensing, collision detection/resolution using ACK frame in the MAC sub layer, back-off time = random amount for non-persistent, no back-off time for 1-persistent, one time unit (T_prop) for p-persistent
• CSMA/CD : collision detection by carrier sensing at layer 1 without ACK frame in the MAC sub layer (ACK may be used by LLC type2), back-off time = [0, 2^k-1] binary exponential back-off time, k is # of transmission failures or attempts

Pure ALOHA vs. slotted ALOHA

• How does pure ALOHA differ from slotted ALOHA?

1. Pure ALOHA는 각 station들이 임의 시간에 TX 시작.
2. Slotted ALOHA는 시간을 slot으로 나눠 sation들이 slot 시작시간에만 TX 하도록 sync을 맞춤.
3. 공통점) sender는 receiver가 보내는 ACK frame으로 collision 여부를 판단, TX failure 시 random amount of time 만큼 쉬었다가 다시 TX.

• Why is the vulnerable time of slotted ALOHA reduced to half of that of pure ALOHA?

1. Pure ALOHA 에서는 (다른 TX 중 내가 TX를 시작하는 경우), (내가 TX 중 다른 TX가 발생하는 경우) 모두 collision 발생
2. Slotted ALOHA 에서는 특정 slot 안에 발생한 TX attempt들은 모두 hold 했다가 다음 slot 시작할 때 TX를 하므로 해당 slot에서 진행 중인 TX에는 영향(collision)을 주지 않음. 즉 pure ALOHA에서는 collision이 발생하게 되는 (다른 TX 중 내가 TX를 시작하는 경우) 가 slotted ALOHA 에서는 제거되고 따라서 Slotted ALOHA에서는 collision이 발생할 수 있는 TX attempt 패턴이 pure ALOHA 보다 반으로 줄어듬.

• Utilization, U (frame time 동안 몇 개(0과 1사이값)의 frame을 보낼 수 있을까?)

1. Pure ALOHA) U =  Ge-2G ;  e-2G 는 성공적으로 보낼 확률; U=0.18 with G=0.5 이 말은 네트워크에 단위시간 당 평균 0.5개의 frame을 전송할 경우 collision domain에서 공유하는 링크 대역폭의 최대 18%만 사용할 수 있다는 의미임.
2. Slotted ALOHA) U= Ge-G ; e-G 는 성공적으로 보낼 확률; U=0.37 with G=1 이 말은 네트워크에 단위시간 당 평균 1개의 frame을 전송했을 때 링크 대역폭의 최대 37%를 사용하는 성능임. 
3. G = Network load;  (collision domain 안에서 스테이션들의 TX 패턴을 포아송 분포로 흩어져있을 때) 단위시간(frame time) 당 평균 몇번의 TX 시도 가 발생하였나는 나타내는 지표임.
4. 정리하면 Slotted ALOHA는 vulnerable time을 줄여 하나의 TX 가 collision 없이 성공적으로 완료될 확률을 높여 pure ALOHA 보다 더 높은 load 의 상황에서도 약 두 배의 높은 링크 효율(throughput도 당연히)이 난다.

• What is a cost of the slotted ALOHA to reduce collision? 

1. Collision domain 안의 station들이 동일한 clock time을 유지해야하는 방법을 추가로 구현해야함.

CSMA

1. What are pros/cons of nonpersistent and 1-persistent CSMA respectively?
2. Nonpersistent is not good for low-load network due to idle time, which reduces link efficiency and increases the unnecessary end-to-end delay, while 1-persistent is good for low-load network.
3. If we were to choose between two protocols for high-load networks, which would you like to pick? Nonpersistent CSMA would generate higher throughput than 1-persistent CSMA in high-load networks since 1-persistent CSMA increases collision due to high overload.
4. CSMA works better and increases throughput in the network with shorter propagation time and larger frame size. It is because CSMA senses a carrier before sending a frame in order to avoid collision and waits for ACK after sending the frame in order to check the success of deliver.
5. What are similarities and differences between ALOHA and CSMA? Both transmit all bits of a frame and wait for ACK for inferring collision.

CSMA/CD

• 1-persistent CSMA with BEB (Binary Exponential Backoff)
• Why CSMA/CD requires (transmission time >= 2 x end-to-end propagation time)?

1. It is because a transmitter can detect collision during transmission. CSMA/CD는 CSMA처럼 전송 시작 전에도 carrier sensing을 하고 추가로 CSMA와는 달리 transmission time 동안만 계속 carrier sensing을 한다. 전송 중 발생하는 collision을 모두 감지하기 위해서는 transmission time이 가장 멀리 떨어진 두 station사이에 충돌 후 jamming signal이 올 때까지 소요되는 시간 (slot time), 즉, 2 x end-to-end propagation time 만큼은 길어야 한다.
2. If a frame is small and thus the transmission time is not long enough, then collision detection fails and CSMA/CD becomes less effective and yield worse performance than CSMA because CSMA/CD does not use ACK unlike CSMA.
3. Slot time은 (버스 링크의 양쪽 끝에 A와 D가 연결되어 있다고 가정할 경우) A를 출발한 신호가 D에 도착할 즈음 collision이 발생하여 D가 전송한 jamming signal을 A가 받기까지 필요한 시간, 즉 collision을 제대로 감지하기 위해 필요한 최소시간 (the time required for a signal to traverse from one end of the network to another, plus the time required to send the jam signal in case of collision)을 의미함. 
4. 따라서, CSMA/CD가 collision을 제대로 감지하기 위한 조건을 slot time으로 설명하면,
5. (1) Frame 전송 중에 충돌 감지를 위해, Ttrans은 slot time 보다는 작으면 안됨 즉, slot time <= Trans
6. (2) Collision 발생시 slot time 안에 jamming 신호를 받아야 하므로, max. round-trip propagation delay는 slot time 보다 커서는 안됨. 즉, (2 x e2eTprop) ≤ slot time 
7. 10Mbps Ethernet의 slot time은 IEEE 802.3 표준에서 51.2 microsecond로 정해놓고 있다. (1)에 의해 10Mbps 링크를  사용할 때, MAC 프레임 크기는 최소 (51.2 x 10^-6 x 10 x 10^6 =) 512bit = 64bytes 가 되야 CSMA/CD가 정상적으로 작동할 수 있다.
8. 만일 frame size (L)이 1500 byte이고 링크 속도(R)이 100Mbps 일때 신호 전파 속도(V)를 3 x 10^8 로 가정하면 링크 길이(d)는 최대 (   18000        )meter를 넘지 않아야 CSMA/CD가 제대로 동작하게 된다. / 이때 만일 링크 속도만 100Gbps로 높이면 d의 길에 대한 조건이 더 까다로와 져서 (    18       ) meter 를 넘지 않아야 한다. 
9. 500m 길이의 100Mbps 링크 양끝에 스테이션 A와 D가 연결되어있고, CSMA/CD를 이용하여 통신하고 있다. 이 링크의 propagation delay는 10microsecond/km 라고 가정할 때, 만일 A가 전송을 시작한 후 D 에서 collision이 발생하였다면 A는 전체 frame 중 ( 1000  ) bits 만 전송하고나서 collision 감지로 인해 전송을 멈추게된다. 반면 CSMA는 전체 frame을 모두 전송하고도 이후 최소 2 x end-to-end propagation time 이상은 대기해야 (ACK을 받지 못해서) collision을 유추하게된다.

 

Binary Exponential Backoff (BEB)

1. How does it work?
2. How does BEB make CSMA/CD efficient, i.e., what is a rational of BEB idea?  Network gets congested (heavier) => more back-off time => less probability of collision
3. What is a drawback of BEB? Stations with more transmission attempts are less likely to be transmitted.==> unfairness (TX 경쟁에 늦에 진입한 station이 이미 여러번 collision을 겪는 station 보다 TX를 할 확률이 더 높다.)

MAC 주소

• 6 octets 즉 48 bits 로 IP 주소와는 다르게 구조를 가지고 있지 않아 지역적인 정보를 포함하지 않는다. 
• 단, 6 octet 중 첫번째 octet의 LSB가 0면 unicast 주소를 1이면 multicast 주로를 의미한다. 예를 들어 MAC 주소가 0x446A03015C49 인 경우, 0x44가 첫번째 octet이고 0x44 는 이진수로 01000100 이다. 여기서 LSB가 0이므로 이 MAC 주소는 unicast 주소 이다.

History of Ethernet

• Traditional shared Ethernet (10Mbps) is half-duplex using a hub (only one station can transmit at a time) and thus they require CSMA/CD. Up to 1Gbps Ethernet can be implemented using half-duplex NICs and a hub.
• What are two technologies required to work CSMA/CD well in the half-duplex 1G Ethernet? 

1. Carrier extension : 조건에 맞지 않게 길이가 짧은 MAC frame 뒤에 의미없는 값인 extension 해더를 추가하여 전송.
2. Frame bursting : 만일 짧은 Frame 여러 개를 연속적으로 전송하게 될때는 각 frame에 extension을 추가하는 방법 보다, 여러 개의 짧은 frame을 하나의 TX 로 전송하여, collision을 감지할 만큼의 충분한 TX 시간을 얻는 frame bursting 방법이 불필요한 정보를 추가로 전송하지 않아서 carrier extension 방법보다 링크 효율이 더 좋음.

• High-speed switched Ethernet is full-duplex (a station can transmit and receive at the same time, and two stations can transmit at a time) and thus it does NOT require CSMA/CD. However, it complies with the previous frame format for “backward compatibility”.

Multilane Distribution (MLD)

• 100-Gbps Ethernet 즉 고속 전송을 구현하는 기술
• break a large frame into 66-bit word 
• and transmits each in multiple parallel channels.

Virtual LAN

• “Some stations belong to the same LAN” means that they are in the same broadcast domain.
• Can you explain the reasons why there are multiple LANs instead of one LAN?
• What is a virtual LAN?
• When we need to form VLANs?
• How to configure VLAN membership?
• Communication between stations in the different VLANs requires layer 3 routing function since they are in different LANs (different IP subnets) 
• 서로 다른 VLAN에 속한 station들 간의 통신은 반드시 L3 routing 즉 IP address 기반 라우팅이 필요하다. 이를 위해 라우터 혹은 Layer-3 switch가 필요하다. (L3-SW 는 MAC 주소기반 L2 routing과 IP 주소 기반 L3 라우팅을 모두 할 수 있으나 기존의 라우터에서 하는 edge 기능 (firewall, NAT, Tunneling, QoS 등)이 없으므로 LAN과 WAN의 경계 즉, border 장비로는 사용되지 않는다.)