콘텐츠로 건너뛰기

Modeling the Internet from the scratch: Link-layer, LAN, Switch

Modeling the Internet

Although I took the CS network course when I’m an undergraduate and read the books related to networks, I still cannot see the whole picture of the network and still don’t understand very well how each layer interacts. So I decided to implement each layer one by one to deeply understand each layer and protocol.

vnet’ is the name of this hobby project. The main purpose of this project is to implement each layer in software and understand how each layer works interact. But I think after I built this, there are various ways to extends this. One thing is a developer can implement his/her own protocol and adapt to ‘vnet’. Then users who joined in ‘vnet’ could communicate with that protocol.

Link-layer Overview

So started from link-layer. The main concern of the link-layer is to transport data from one node to an adjacent node over a link.

In this post, the abstracted word node is referring to any device that runs a link-layer protocol. So this could be host, router, switch.

Link is communication channels that connect with adjacent nodes and in order to transfer data from source node to destination node, it must be moved over link.

The boundary between the host and the link is called an interface. The host typically has only a single link and the router has multiple interfaces, one for each of its links.

There are other important services for the link-layer. Those could be medium access control (MAC) for reliable delivery of data and error detection and correction on the bit level.

Most of the link-layer is implemented on hardware

link-layer on physical view
link-layer on physical view

Such services we listed above most of them are implemented on hardware especially on the network adapter. Like this, most of the protocol such as MAC and error detection is for a hardware problem. But I’m still want to see how on link-layer, each node could send data to an adjacent node over the link.

So I decided to abstract them all away! I assume that there’s no multiple access problem, no error on the bit level.

package na
// Card is abstracted network adapter part to simulate bytes transport on
// physical cable. Node's interface uses this interface to send frame
// between nodes.
type Card interface {
Send(buf []byte, addr string) (time.Time, error)
Recv() <-chan *FrameData
}
view raw comm.go hosted with ❤ by GitHub

For abstracting all those things, defined interface. Card represents a network adapter and the interface will own it. In the project, the concrete type of Card implementing this interface use UDP for ease.

Define the link-layer network topology

To model our link-layer network, first, we need to define basic topology things. We can think that the link-layer network could be represented with the concept of “link” and its two “endpoint” and machine-thing has one or more “endpoint”.

package link
type Link struct {
cost uint
ep1 EndPoint
ep2 EndPoint
}
func (l *Link) AttachEndpoint(ep EndPoint) error {
}
// Opposite returns other endpoint of given id. If other endpoint does not exist,
// then return error
func (l *Link) Opposite(id Id) (EndPoint, error) {
}
// EndPoint represents point of link. Link is the channel to pass data to end-point
// either side to the opposite
type EndPoint interface {
Id() Id
GetLink() *Link
AttachLink(link *Link) error
}
view raw host.go hosted with ❤ by GitHub

With Transmitter we can send frame data to the link. And Interface extends this with the Endpoint interface. Also when we talked about the MAC address, the MAC address is assigned to each network interface and Host owns it. As a result, Interface has Address() a method that returns MAC address.

In the Host struct, there are several important components besides Interface.

  • NetHandler : With NetHandler, when Host receives frame from Interface , after doing its own business logic, we can pass the network-layer payload bytes to the network-layer.
  • FrameEncoder: When we want to send frame data to another node, we need to serialize frame data into bytes
  • FrameDecoder: When we receive frame data bytes from another node, we first need to deserialize it into frame data structure using FrameDecoder

Switch

There’s one important concept left when we talk about LAN: “switch”.

The switch has two key features. One is “filtering” which is a function that determines whether the frame it receives should be forwarded or just dropped. And the second one is “forwarding” which sends the frame it receives from one of the switch’s ports to the outgoing link.

All these features are done by a “switch table”. The switch table contains the following information:

  • MAC address
  • The switch port that leads toward that MAC address
  • The timestamp at which the entry was created.

So we could struct our switch and switch table like this:

type ForwardEntry struct {
// Incoming is port id attached to switch
Incoming Id
// Addr is destination node address
Addr types.HwAddr
// Time is timestamp when this entry is created
Time time.Time
}
type FrameForwardTable struct {
entries []ForwardEntry
}
type Switch struct {
PortList map[Id]Port
Table *FrameForwardTable
frmDec *FrameDecoder
frmEnc *FrameEncoder
}
view raw swch.go hosted with ❤ by GitHub

Switch contains its own port list and switch table. Remember that switch do not have MAC addresses with their ports that connect to hosts and routers. So we need to model the port as such.

// Port can transmit data and can be point of link. But it has no hardware
// address. Before using Port, it must register its own Id
type Port interface {
Transmitter
EndPoint
Register(id Id)
Registered() bool
}
view raw port.go hosted with ❤ by GitHub

Port has its own id, not link-layer address so we need to register its own id. The concrete port instance is not initiated with its own id. The registerer such as a switch or other client assigns an id to each port then attached to the switch.

Filtering, Forwarding Algorithm

Then how the switch can filter and forward the frame to other hosts or router? Let’s take a simple scenario: A frame with destination address “62-FE-E7–11–89-A3” arrives at the switch on port with the id of “1”.

First, the switch updates its switch table with the following tuple data:

  • The MAC address in the frame’s source address
  • The interface from which the frame arrived
  • The current time.

Then there could be three possible scenarios:

  1. If there is no entry for MAC address “62-FE-E7–11–89-A3” in the table. In this case switch broadcast receiving frame to the ports which it has except the port where it receives the frame.
  2. If there is an entry for MAC address “62-FE-E7–11–89-A3” and port id “1”, in this case, because this means that the destination node is located on port “1”, there’s no need to forward the frame once again. As a result, the switch performs the filtering function by discarding the frame.
  3. If there is an entry for MAC address “62-FE-E7–11–89-A3” and port id is NOT “1” (let’s say the entry has port id “2”). In this case, the switch forwards the frame to port id “2”

This is the basic algorithm of how the switch filter and forward frame to the other nodes.

// Forward receives id of port it receives frame, address of sender
// and frame to send to receiver. Based on id and address it determines whether to
// broadcast frame or forward it to others, otherwise just discard frame.
func (s *Switch) Forward(incoming Id, frame na.Frame) error {
s.Table.Update(incoming, frame.Src)
frm, err := s.frmEnc.Encode(frame)
if err != nil {
return err
}
entry, ok := s.Table.LookupByAddr(frame.Dest)
if !ok {
return s.broadcastExcept(incoming, frm)
}
if entry.Incoming.Equal(incoming) {
log.Printf("discard frame from id: %s, src: %s, dest: %s\n", incoming, frame.Src, frame.Dest)
return nil
}
p := s.PortList[entry.Incoming]
if err := p.Transmit(frm); err != nil {
return err
}
return nil
}
view raw swch.go hosted with ❤ by GitHub

The switch deletes an entry in the table if no frames are receives with that address as a source address for some times. We call it an aging time. With this mechanism, we could handle the scenario when the host machine is replaced with another so that it has a different network adapter, MAC address, the switch could delete outdated data.

Also, we can see why the switch is “transparent”. It is because the switch is doing its job without the host or router having to know the switch link-layer address. So when we move on to the next level “network-layer”, we cannot see the presence of a switch.

Construct the link-layer network

So far, we’ve seen all the basic components of LAN from the view of the link-layer level. Let’s build a simple link-layer network.

sample link-layer network diagram
sample link-layer network diagram
  • In this network, there are two switches (“switch1”, “switch2”) and three hosts (“host1”, “host2”, “host3”).
  • On “switch1”, there are three ports, and each connected with “host1”, “host2”, “switch2”.
  • On “switch2”, there are two ports, and each connected with “switch1” and “host3”.

First, we need to setup five node.

func Build() (host1 *link.Host, host2 *link.Host, host3 *link.Host,
swch1 *link.Switch, swch2 *link.Switch) {
// setup node
host1 = link.NewHost()
host2 = link.NewHost()
host3 = link.NewHost()
swch1 = link.NewSwitch()
swch2 = link.NewSwitch()
}
view raw network.go hosted with ❤ by GitHub
construct the network — define node

Then we need to create the endpoint (interface or port) and attach it to its node: Interface for the host, the port for the switch.

And underneath, all the frame transmission is done by UDP we need to specify UDP port (4001–40008).

Each host has one interface with the variable name (intf1intf2intf3). And each switch has multiple ports with the variable name (sp11sp12sp13 for switch1, sp21sp22 for switch2)

func Build() (host1 *link.Host, host2 *link.Host, host3 *link.Host,
swch1 *link.Switch, swch2 *link.Switch) {
// setup node
// setup interface
intf1 := link.NewInterface(40001, link.AddrFromStr("11-11-11-11-11-11"), host1)
attachInterface(host1, intf1)
intf2 := link.NewInterface(40002, link.AddrFromStr("22-22-22-22-22-22"), host2)
attachInterface(host2, intf2)
intf3 := link.NewInterface(40003, link.AddrFromStr("33-33-33-33-33-33"), host3)
attachInterface(host3, intf3)
sp11 := link.NewSwitchPort(40004, swch1)
sp12 := link.NewSwitchPort(40005, swch1)
sp13 := link.NewSwitchPort(40006, swch1)
attachSwchInterface(swch1, sp11, "1")
attachSwchInterface(swch1, sp12, "2")
attachSwchInterface(swch1, sp13, "3")
sp21 := link.NewSwitchPort(40007, swch2)
sp22 := link.NewSwitchPort(40008, swch2)
attachSwchInterface(swch2, sp21, "1")
attachSwchInterface(swch2, sp22, "2")
}
view raw network.go hosted with ❤ by GitHub
construct the network — setup interface and attach it to node

Finally, we connect two endpoints with the link. To match with the diagram, we need to connect (intf1sp11), (intf2sp12), (sp21sp13) and (intf3sp22).

Then using these, we can simulate various cases of link-layer frame transmission tests.

func Build() (host1 *link.Host, host2 *link.Host, host3 *link.Host,
swch1 *link.Switch, swch2 *link.Switch) {
// setup node
// setup interface
// setup link
link1 := link.NewLink(1)
attachLink(intf1, link1)
attachLink(sp11, link1)
link2 := link.NewLink(1)
attachLink(intf2, link2)
attachLink(sp12, link2)
link3 := link.NewLink(1)
attachLink(sp13, link3)
attachLink(sp21, link3)
link4 := link.NewLink(1)
attachLink(sp22, link4)
attachLink(intf3, link4)
return
}
view raw network.go hosted with ❤ by GitHub
construct the network — 3: attach the link to interfaces

You can find it on github

Leave a comment