Project SLIP

This page as PDF

Simple Scalable Local Intranet Protocol

Reliable Communication Protocol SLIP

SLIP is scalable with respect to network size (address size class (ASC), ranging from 4 to 16 bit), maximal data payload (data size class (DSC), ranging from 4 to 16 bit length) and the network topology dimension size (address dimension class (ADC), ranging from 1 to 4).

Network nodes are connected using (serial) point-to-point links, and they are arranged along different metric axes of different geometrical dimensions: a one-dimensional network (ADC=1) implements chains and rings, a two-dimensional network (ADC=2) can implement mesh grids, a three-dimensional (ADC=3) can implement cubes, and so on. Both incomplete (missing links) and irregular networks (with missing nodes and links) are supported for each dimension class.

The main problem in message-based communication is routing and thus addressing of nodes. Absolute and unique addressing of nodes in a high-density sensor network is not suitable. An alternative routing strategy is delta-distance routing, used by SLIP. A delta-distance vector Δ specifies the way from the source to a destination node counting the number of node hops for each dimension.

A message packet contains a header descriptor specifying the type of the packet and the scalable parameters ASC,DSC and ADC, shown in Tab. 2. There are two different main message types: requests and replies. A packet descriptor follows the header descriptor, containing: the actual delta-vector Δ ,the original delta-vector Δ0, a preferred routing direction ω, an application layer port π, a backward-propagation vector Γ, and the length of the following data part. The total bit length of the packet header ranges from 39 up to 228 bits depending on {ASC,DSC,ADC } scalable parameter tuple setting, which optimises application specific the overhead and energy efficiency (spatial & temporal). Each time a packet is forwarded (routed) in some direction, the delta-vector is decreased (magnitude) in the respective dimension entry. There are different smart routing rules, applied in order showed below until the packet can be routed (or discarded). First the normal XY routing is tried, where the packet is routed in each direction one after another with the goal to minimize the delta count of each particular direction. If this is not possible (due to missing connectivity), the packet is tried to send to the opposite direction, marked in the gamma entry part of the message packet descriptor. Opposite routing is used to escape small area traps, backward routing is used to escape large area traps or to send the packet back to the source node (packet not deliverable).

Entry

Size [bits/Bytes]

Description

HDT:ADC

2b

Address Dimension Class

HDT:ASC

2b

Address Size Class

HDT:DSC

2b

Data Size Class

HDT:TYP

2b

Message type = {Request, Reply, Alive, Acknowledge}

PDT

PDT

Actual delta vector

PDT0

PDT

Original delta vector

PDT

PDT

Backward propagation vector

PDT

PDT

Preferred routing direction

PDT

PDT

Application layer port

PDT:LEN

PDT:LEN

Length of packet

DATA

DATA

Data

Tab. 2:  SLIP message format (HDT: header descriptor, PDT: packet descriptor)

A message is only send to a neighbour node using the particular link iff the connection to the neighbour node was negotiated and is fully operational concerning the sending and the receiving of messages to and from the neighbour node. For this purpose, the communication sends periodically ALIVE messages to all direct surrounding nodes and waits for ACKNOWLEDGE messages send back from the neighbour node to check the state of a connection. Non-existing nodes can be detected this way, too.

M:  Message(Δ,Δ0,Γ,ω,π,Len,Data)
 PRO smart_route(M):
    IF Δ=0  THEN  DELIVER(M,π)ELSE
    TRY  route_normal(M)  ELSE
    TRY  route_opposite(M)  ELSE
    TRY  route_backward(M)  ELSE  DISCARD(M);

Ex. 1 Smart Routing Protocol SLIP (simplified)

The hardware implementation (using Conpro and standard cell ASIC synthesis) requires about 244k gates, 15k FF 2.5mm2 assuming ASIC standard cell technology 0.18µm. The design is partitioned on programming level in 34 processes, communicating by using 16 queues.

Robustness and Stability Analysis

A simulation of a sensor network consisting nodes arranged in a two-dimensional matrix with 10 rows and 10 columns was performed by using a multi-agent model. Messages and sensor nodes were modeled with agents.  A path is operational (reachable) iff a node (device under test), for example node at position (2,2), can deliver a request message to a destination node at position (x,y) with x2 y2,and a reply can be delivered back to the requesting node. A failure of a specific link and node results in a broken connection between two nodes.

With traditional XY routing there is a strong decrease of operational paths, from a specific node (DUT) to any other node, if the number of broken links increases. Using smart routing increases the number of operational paths significantly, especially for considerable damaged networks, up to 50% compared with XY routing providing only 5% reachable paths anymore.