Cloud Computing

These are notes form Cloud Computing and Architecture an O'Reilly book written by George Reese.

• The Cloud
• the cloud is more than just a term for the internet
• specifically it is a combination of software and infrastructure 
• accessible via a web browser
• zero capital expenditure to get started
• pay for uses not initialization
• Software
• Software as a Service (SaaS) term that refers to software in the cloud
• Available via a web browser
• On-Demand Availability
• Payment based on Usage
• Minimal IT demands
• web based deployment model
• does not care about host site
• does not care about operating system or language used to write program
• Example: Gmail
• provides same service as Apple Mail or Outlook but without the client
• Multitenancy
• server based software that supports the deployment of multiple clients in a single software instance
• used as advertisement but virtualization technologies renders benefits moot
• Hardware
• Hardware is requested, i.e. a server but not physically owned by user
• increase in security due to obscurity, 
• Difficulties of proprietary servers
• Capacity planning
• Upfront costs of SAN(storage area networks) or individual servers
• Hardware destruction
• Disaster and recovery i.e. entire servers go down
• Real Estate and Electricity Usage
• Difficulties subsumed into main distributor of cloud resources rather than individual companies creating proprietary networks
• Hardware Virtualization
• Servers can be partitioned into sections with its own memory, CPU, and disk footprints
• Has a significant performance penalty however is a non-issue because
• cloud vendors servers far superior in performance to capabilities of small business servers
• Cloud Storage
• replaces physical storage systems
• Operationally different from physical due to degraded performance but enhanced structure
• Impractical for runtime storage for an application such as for transaction applications
• Cloud Application Architectures
• Grid Computing
• breaks up processing into small chunks that can be processed in isolation
• i.e. SETI@home
• collected volumes of data processed and checked against other users, alternate example BOINC
• functional steps in grid computing
• both worker and manager watch message queue
• worker waits for new data set, pulls data set publish results
• manager reads results
• limited to financial, scientific, and large scale data problems
• Transactional Computing
• one or more pieces of incoming data processed together and establish relationships with data already in the system
• components form a cluster
• Nodes in a transactional system must be long lived rather than short lived in grid computing
• Mean time between failures (MTBF) number of physical nodes governs this so cloud has higher failure rate than proprietary servers, but this can be mitigated
• The Value of Cloud Computing
• IT infrastructure traditional vs cloud
• file server vs google docs, MS outlook vs gmail, server racks and firewall vs Amazon EC2
• Cloud reduces software licensing hassle, charged for use, software upgrades, hardware failure, # of technology assets, manage depreciation of it assets, capacity management
• IT infrastructures without special constraints are extremely expensive to start up compared to cloud services
• The Economics
• Capital Costs
• depreciation of servers and computers
• Cost Comparison
• cloud has no capital costs but has monthly service fees, setup costs, and staff costs
• However many large companies already have infrastructure in place, not necessarily cost effective for them to transition to cloud services
• Cloud Infrastructure Models
• Platform as a Service Vendor
• complete operational and deployment options
• Google App Engine
• Vendor Lock-in i.e. Python requirement for Google Apps
• Infrastructure as a Service
• Amazon Web Services

Back to ToC

Cloud Applications and Architecture ToC

The following is a Table of Contents from Cloud Applications and Architecture an O'Reilly book written by George Reese.

1. Cloud Computing

Back to ToC

Notes - Error Detection and Correction

The following are notes from Computer Networks written by Tanenbaum 5th edition.

• Communication channels have a wide range of characteristics
• We must have a way to deal with errors
• error correction codes
• FEC(Forward Error Correction)
• error detection codes
• both must account for the types of erros that can occur, both have trade offs
• burst error
• single bit error
• sometimes location of an error will be known, erasure channel

Error - Correcting Codes

• four different codes
• Hamming Codes
• Hamming distance, the number of bits that are different between two sequences after exclusive or each bit together
• to reliably detect d errors you need a distance d+1 code
• total length of a block is n = m + r
• n bit code word
• code rate is the fraction of a codeword that carries non redundant information

• example
• 0000000000, 0000011111, 1111100000, 1111111111
• hamming distance of 5 so can correct double errors or quadruple errors
• useful for understanding block codes
• Binary Convolution Codes
• convolution code, no natural size, as incoming bits come in perform some operation

• each input bit produces two output bits on the right hand side that are XOR sums of the input and internal state
• each state is kept in 6 memory registers, each time another bit is inputted all values are shifted to the right, constraint length of this code is k = 7
• Viterbi algorithm
• soft decision decoding determine likeliness of 1, 0
• hard decision decode determine each bit is 0,1 before error correction 
• Reed - Solomon Codes
• linear block codes, systematic
• operates on m bit symbols
• based on fact that every n degree polynomial is determined by n + 1 points so if 2 points are received in error, we can find the third point that will still lie on the line
• defined as polynomials that operate over finite fields, strong error correction properties makes them useful in DSL, CDs, DVDs and Blu-Ray
• Low - Density Parity Check Codes
• LDPC (Low - Density Parity Check Codes)
• each output bit is formed from only a fraction of the input bits
• matrix representation of code with low density of 1s, standard for video broadcasting, 10 Gbps Ethernet and 902.11
• these all add redundancy to the information that is sent
• systematic code, m data bits are sent along with check bits
• linear code check bits are computed as a function of the data bits
• usually using exclusive or

Error - Detecting Codes

• types of codes
• Parity
• parity bit appended to the end of data to make the number of 1s in the codeword even or odd
• 1011010 is sent in even parity it will be sent as 10110100 to signify that its already even by appending the 0
• can only reliably detect single bit error
• interleaving, can have multiple parity bits n x n matrix with parity bits at the end of each
• n+1 burst will still be undetected but now capable of correcting bits
• Checksums
• 16 bit internet checksum used as part of IP
• one's compliment arithmetic
• CRCs(Cyclic Redundancy Checks)
• polynomial code, treats bits as polynomial coefficients

• sender and receiver agree upon generator polynomial G(x) in advance
• algorithm
• let r be degree of G(x) append r zero bits to the low order end of the frame so its now m+r bits
• divide the bit string corresponding to G(x) into the bit string using modulo 2 division
• subtract the remainder using modulo 2 subtraction, the result is checksummed frame to be sent
• example as follows

• with single bit or 2 single bit errors the division will not be able to grant the same checksum if burst length is r+1 the remainder will be zero if and only if the burst is identical to G(x)
• IEE 802 standard is

• detects all bursts of length 32 or less and all bursts that are odd

Back to ToC

Notes - Data Link Layer Design Issues

The following are notes from Computer Networks written by Tanenbaum 5th edition.

• Data link layer uses services of the physical layer to send and receive bits over communication channels
• provide a well defined service interface to the network layer
• deal with transmission errors
• regulate flow of data so that slow receivers are not swamped by fast senders
• data link layer takes packets and encapsulates them into frames for transmission

Services Provided to the Network Layer

• function is to provide services to the network layer
• path data takes shown below

• offers various services
• unack connectionless service
• source machine send independent frames to destination machine
• ack connectionless service
• WiFi (802.11)
• ack connection oriented service
• most sophisticated, source and destination establish reliable data link

Framing

• in order to provide services to network layer, it must use the services provided by the physical layer
• must break up the bit steam using
• Byte Count
• uses a field in the header to specify number of bytes in frame
• can be garbled by transmission error
• rarely used on its own
• Flag Bytes with byte stuffing
• flag bytes used as starting and ending delimiters
• byte stuffing
• sender's data link layer insert a special ESC(escape byte) before each accidental flag byte
• following is an example used in PPP(Point to Point protocols)

• Flag Bits with bit stuffing
• gets around byte stuffing disadvantage that it is tied to 8 bit bytes
• can contain arbitrary bits developed for HDLC(High Level Data Link Control Protocol)

• Physical Layer coding violations
• is a shortcut from the physical layer
• if we do 4B/5B we don't need to map to all possible symbols so the unused signals are violations that signal an error

Error Control

• mark the start and end now we have to see if delivery is in order
• provide sender with some feedback
• introduce timers into data link layer, starts a time so that frame is set to expire
• this way sender knows if frame has been lost
• issue to manage timers

Flow Control

• what to do when a sender wants to transmit frames faster than receiver can accept them
• two approaches are commonly used
• feedback-based flow control receiver sends information to sender to give permission to send
• rate based flow control, built in mechanism to limit rate of sending
• NIC(Network Interface Cards)
• can handle frames as fast as they can arrive so overruns aren't a problem

Back to ToC

Notes - Data Link Layer

The following are notes from Computer Networks written by Tanenbaum 5th edition.

• VLANs(Virtual LANs)
• connections called bridges to join lans together

Uses of Bridges

• Reasons why an organization may have multiple LANs
• Many university and corporate departments have their own LANs
• Organization geographically spread wants to be joined
• Split a single LAN into separate LANs for logical organization
• bridges let LANs be joined while keeping their own capacity
• bridges increases reliability
• can reroute nodes that are malfunctioning giving garbage data
• transparent bridges
• create with backward learning algorithm to stop traffic from being sent to unneeded areas and spanning tree algorithm to break loops

Learning Bridges

• example topology

• bridges developed when classic ethernets were in use
• bridge operates in promiscuous mode accepts every frame to its ports
• chooses to forward or discard
• simple way to implement this scheme is to have a big hash table
• initially empty
• backward learning every frame sent tells the bridge about the topology
• arrival time of frames noted in entry, tells the bridge the last time a frame is seen
• bridge scans and purges entries more than a few minutes old
• routing procedure for incoming frame
• if the port for destination is same as source discard frame
• if destination port is different from source forward to destination
• if destination unknown send frame on all ports except the source
• as each frame arrives algorithm must be applied
• cut through switching/wormhole routing
• bridges only look at MAC addresses to reduce latency

Spanning Tree Bridges

• to increase reliability redundant links used between bridges

• this introduces loops in the topology
• so in order to do this, overlay the topology with a spanning tree to reach every bridge, ignore some links, example as follows

• spanning tree is built with distributed algorithm, bridge periodically broadcasts a configuration message on all ports
• tree of shortest paths from root to every bridge constructed, and spanning tree used between bridges
• Radia Perlman poem

Repeaters, Hubs, Bridges, Switches, Routers and Gateways

• These devices operate in different layers which is why even though they perform similar roles, they are all necessary

• repeaters amplify signals
• hubs don't amplify, but allow for multiple lines
• bridges connects two or more LANs has multiple ports
• isolated in its own collision domain, CSMA/CD not needed
• better performance than hubs
• can join different types of LANs such as Ethernet and Token Ring
• joins different max frame lengths
• join different security protocols
• switches are modern bridges by another name
• utilizes twisted pair cables, often used for ethernet
• routers totally different
• frame header and trailer gets stripped off and the packet located in payload field is passed to routing software
• chooses outgoing line with address
• does not see fram address or where packet comes in on
• transport gateways connect two computers using different connection oriented protocols such as
• TCP/IP
• SCTP
• understands formats such as email into sms messages

Virtual LANs

• early days of LAN setup was designed in this way

• issues
• difficult to replace, geographically new workers have to sit at open workstations instead of with their coworkers
• load issue not even
• broadcast traffic to reach correct persons
• vulnerable to broadcast storm when LAN malfunctions and sends random messages
• solution is to set up VLAN(Virtual LAN)
• based on VLAN aware switches
• network admin decides how many VLANs are possible
• association as configuration tables are built into bridges
• The IEEE 802.1Q Standard
• To implement this scheme bridges need to  know which VLAN an incoming 
• issues
• do we need to throw out existing ethernet cards to accomodate this standard?
• who generates fields?
• what happens to max size frames
• VLAN fields are only used by bridges and switches and not by user machines

• bridge is also allowed to use higher layer protocol to select colors for VLAN creation

• for 802.1Q Ethernet frames, the tag composed of
• 3 bit priority field
• CFI(Canonical Format Indicator)
• indicate order of bits in MAC adress
• VLAN Identifier specifies color of VLAN
• when this comes to VLAN aware switch the identifier is matched to a table to figure out which ports it should send to

Back to ToC

Notes - RFID

The following are notes from Computer Networks written by Tanenbaum 5th edition.

• RFID(Radio Frequency Identification)
• EPC(Electronic Product Code)
• commercialized by EPCglobal

EPC Gen 2 Architecture

• communicates via the RFID Reader which sends out a signal that gets scatted back by a RFID tag
• EPC gives each tag 96 bit EPC identifier 

• readers have all the intelligence, much more powerful and do all signal processing

EPC Gen 2 Physical Layer

• sent in the UHF(Ultra High Frequency) range
• readers and tags use ASK(Amplitude shift keying) modulation to encode bits

EPC Gen 2 Tag Identification layer

• situation is multiple access problem
• closest protocol is slotted ALOHA protocol

• tags pick a random slot to reply with
• sends a short 16 bit random number for collision reader receives and sends ACK to acquire slot and send EPC identifier
• adjust number of slot, reader can send QAdjust message to change slot adjust level for RFID tags

Tag Identification Message Formats

• Form of the Query Message

• Command field identifies this as query
• DR, M, TR determine physical layer parameters
• Sel, session and target select the tags to respond tags keep track of up to 4 concurrent sessions
• Q defines the range of slots that tags can respond to 0 to 2^Q-1
• CRC to protect the fields
• grown to resemble very small computers Internet of Things

Back to ToC

Notes - Bluetooth

The following are notes from Computer Networks written by Tanenbaum 5th edition.

• developed by Ericsson, IBM, Nokia, Intel, and Toshiba in a SIG(Special Interest Group)
• bluetooth utilizes pairing to securely transfer data between mobile devices

Bluetooth Architecture

• piconet a master node with up to seven slave nodes
• multiple piconets can be connected into a scatternet
• up to 255 parked nodes in a set, master set these devices into a low power state to reduce drain on batteries
• at its heart is a TDM system

Bluetooth Applications

• most network protocols provide channels
• Bluetooth provides applications called profiles
• 6 are for audio and video
• human interface profile such as keyboards and mice
• profiles for networking
• personal area network profile, ad hoc network or remote access to another network through an AP
• profiles for higher level info exchange

The Bluetooth Protocol Stack

• loose group into layers does not follow OSI or TCP/IP or the 802 model
• layer description here

• bottom layer is the physical radio layer
• link control is baseband layer similar to MAC sublayer with some physical layer
• two protocols to use link control
• link manager
• establishment channels, pairing and encryption, QoS
• below the line implemented on the chip
• L2CAP(Logical Link Control Adaptation Protocol)
• frames variable length messages and provides reliability as needed
• many protocols use this
• Top layer is where applications are located
• profiles are vertical boxes because they define a slice of the protocol stack

The Bluetooth Radio Layer

• radio layer moves bis from master to slave, operating range 10 meters
• uses adaptive frequency hopping
• 3 forms of modulation used to send bits
• frequency shift keying to send a 1 bit symbol every microsecond
• 2 or 3 bit enhanced rates introduced in 2.0 used for only data portion of frame

The Bluetooth Link Layers

• link control or baseband layer close to MAC
• turns the raw bit stream into frames and defines formats
• piconet defines 625 microsecond time slots
• frames 1, 3, 5 slots long
• overhead of 126 bits for access code and header, settling time of 250-260 microseconds per hop to allow for stability
• 5 slot frame much more efficient than 1 slot frame
• link manager sets up channels called links using pairing procedure, configured with same PIN(Personal Identification Number)
• SCO (Synchronous Connection Oriented)
• used for real time data
• fixed slot in each direction
• ACL (Asynchronous Connectionless Link) 
• used for packet switched data
• sent over L2CAP layer
• accepts packets of up to 64KB from upper layers breaks them into frames
• handles multiplexing/demultiplexing of multiple packet sources
• handles error control and retransmission

The Bluetooth Frame Structure

• defines several formats, two types of frames

• Header field
• Adress identifies which of the 8 active devices we can go for
• type identifies ACL, SCO, poll, or null
• Flow assert by slave when buffer is full
• ack is for acknowledgements
• Sequence is to number the frames for transmission, since its stop and wait protocol only need one bit
• 8 bit checksum
• entire header repeated 3 times for error correction, if all 3 same received, if not majority option is accepted
• data field has its own formatting

Back to ToC

Notes - Broadband Wireless

The following are notes from Computer Networks written by Tanenbaum 5th edition.

• Broadband wireless, large antenna on a hill easier than digging many trenches for cables
• 802.16 WiMAX(Worldwide Interoperability for Microwave Access)
• fairly complicated like OSI so there is a WiMAX forum to define standards

Comparison of 802.16 with 802.11 and 3G

• why not just use 802.11 or 3G?
• more akin to 4 G combines both aspects
• connect devices to internet at megabit/sec speeds without cable or DSL
• designed to
• carry IP packets over air
• peer to peer VoIP stream media
• OFD based technology
• more like 3G in that
• tries to achieve high capacity
• uses more power and better antennas
• licensed spectrum around 2.5 GHz
• LTE(Long term evolution)
• collision course with 4G

The 802.16 Architecture and Protocol Stack

• base stations connect directly into backbone network, air interface to mobile and subscriber stations
• the following is the protocol stack 

The 802.16 Physical Layer

• utilizes 3.5 GHz or 2.5 GHZ
• transmissions over OFDM
• Symbols are sent with QPSK, QAM-16, QAM-64
• SNR ratio in order to reach distant stations use QPSK sends 2 bits per symbol coded for forward error correction
• common for noisy channels to tolerate bit erros
• 802.16 developers did not like certain parts of GSM and DAMPS
• chose flexible scheme OFDMA(Orthogonal Frequency Division Multiple Access)
• different sets of subcarriers so that more than one station can send/receive at once
• also chose to use TDD(Time Division Duplex) to alternate between sending and receiving
• could have done FDD(Frequency Division Duplex) but this is not as flexible and harder to implement

• one of new uplink bursts reserved for ranging
• process by which new stations adjust timing and request initial bandwidth during base station setup
• is a hope and transmit setup assumes no collision

The 802.16 MAC Sublayer Protocol

• data link layer divided into 3 sublayers
• encryption to keep data secret
• perform mutual authentication using RSA public-key cryptography using X.509 certificates
• Uplink Channel Services
• Constant bit rate service
• transmit voice
• Real-time variable bit rate service
• transmit multimedia
• Non Real-time variable bit rate service
• file transfer
• Best effort service
• everything else
• ethernet binary exponential backoff algorithm used
• all are connection oriented

The 802.16 Frame Structure

• All MAC frames begin with generic header, followed by CRC
• checksum surprisingly optional since no attempt is made to retransmit

• Generic Frame
• EC bit tells whether payload is encrypted
• type identifies frame type
• tells whether packing and fragmentation are present
• CI indicates presence or absence of checksum
• EK tells which encryption is being used
• length gives complete length of entire frame
• connection identifier tells which connection this frame belongs too
• Header CRC uses polynomial x⁸ + x² + x + 1
• Bandwidth request frame is different, starts with 1 bit instead of 0 and is just a command

Back to ToC

Notes - Wireless LANs

The following are notes from Computer Networks written by Tanenbaum 5th edition.

• wireless LAN standard 802.11

The 802.11 Architecture and Protocol Stack

• connect clients via AP(Access Points)
• several access points can be connected together in a distribution system
• ad hoc network also possible, computers can directly send frames to each other
• structure is as follows

• transmission techniques of frequency hopping and infrared are now defunct
• spread spectrum is now known as 802.11b
• OFDM is 802.11a
• multiple antenna techniques now caled 802.11n

The 802.11 Physical Layer

• transmission techniques make it possible to send a MAC frame over the air from one station to another
• short range radios in 2.4GHz or 5 GHz ISM frequency bands
• rate adaptation
• if signal is weak low rate can be used, if clear highest rate can be used
• 802.11b
• spread spectrum similar to CDMA but there is only one spreading code
• satisfy FCC requirement
• Barker sequence
• autocorrelation is low
• send at rate of 1 Mbps Barker sequence used with BPSK modulation to send 1 bit per 11 chips, 11 Mchips /second
• send at 2Mbps used with QPSK modulation to send 2 bits per 11 chips
• CCK(Complementary Code keying)
• 802.11a
• up to 54Mbps in 5 GHz band
• uses OFDM(Orthogonal Frequency Division Multiplexing)
• sent over 52 subcarriers
• 802.11g
• copies 802.11a operates in 2.4GHz ISM band
• 802.11n
• throughput of 100Mbps
• doubled channels to 40 MHz
• signal streams uses 4 antennas to transmit 4 streams at the same time
• separated using MIMO(Multiple Input Multiple Output) communication techniques

The 802.11 MAC Sublayer Protocol

• radios are half duplex
• avoids collision using CSMA/CA (CSMA with collision avoidance)
• station using channel sensing, exponential backoff 0-15 in the case of OFDM physical layer

• DCF(Distributed Coordination Function)
• starting backoffs early
• acks are used to infer collisions
• no central control
• PCF(Point Coordination Function)
• AP controls activity in cell like base station
• in practice not used
• transmission ranges of different stations may be different, exposed/hidden terminal problem

• NAV(Network Allocation Vector)
• each station keep record of when channel is in use
• how long a frame will take to complete
• Channel sensing

• RTS is right to send CTS is clear to send
• has issues, does not help short frames 
• can slow down operation
• Wireless networks are noisy and unreliable
• strategies
• lower the transmission rates use more robust modulation
• if too many frames lost can lower the rate again
• probability of receiving an n bit frame entirely correctly is (1-p)ⁿ
• very difficult to receive full frame for long frame, ethernet frame has less than 30% success
• fragmentation to split packets into smaller sizes to reduce error
• power saving beacon frames
• frames advertises the presence of AP every 100 msec
• clients set a power management bit to tell it that they are entering power save mode
• will buffer traffic to power save mode nodes
• APSD (Automatic Power Save Delivery)
• sends buffer frames to clients just after client sends frames to AP
• works well for VoIP wireless phones
• QoS suffers with wireless to prevent this we have to make VoIP services higher priority
• intervals after an ack in CSMA/CA
• SIFS(Short InterFrame Spacing)
• control frame or next fragment sent here
• AIFS(Arbitration InterFrame Spacing)
• there is a high priority and low priority frame here
• DIFS(DCF InterFrame Spacing)
• regular frame
• EIFS(Extended InterFrame Spacing)
• bad frame recovery done

• TXOP or transmission opportunity
• original CSMA/CA mechanisms let stations send one at a time
• slows down fast senders to speed of slow senders
• rate anomaly

The 802.11 Frame Structure

• 802.11 standard defines 3 classes of frames
• data
• control
• management
• variety of fields used within the MAC sublayer

• Frame control made up of 11 subfields
• version set to 00 though allows future versions to be created
• type data control or management
• subtype RTS or CTS
• To DS From DS is whether the frame is incoming or going to APs
• More fragments mean more fragments will follow
• Retry is retransmission
• Power management means to go into power save mode
• More data means more frames incoming
• Protected frame means encryption has occurred
• Order tells that the frames will come in order
• Duration how long frame and ack will occupy channel
• Addresses to source and destination, 3rd can be a final destination and second is a relay point
• sequence numbers frames so duplicates can be detected
• data stores data, and check sequence is a 32 bit CRC

Services

• Association service used by mobile stations to connect themselves to APs
• Reassociation is to change preferred AP
• disassociation to break AP
• Authenticate to choose security
• recommend scheme WPA2(WiFi Protected Access 2)
• outdated scheme is WEP(Wired Equivalent Privacy)
• based on AES(Advanced Encryption Standard)
• distribution service determines routing
• integration service handles translation for frame to be sent outside a LAN
• data delivery service
• QOS traffic scheduling
• traffic with different priorities
• Transmit power control service to meat power limitations, dynamic frequency selection to avoid transmitting on reserved frequencies

Back to ToC

Notes - The Network Layer in the Internet

The following are notes from Tanenbaum's Computer Networks 5th Edition.

• Principles of Network Layer Design
• Make sure it works
• do not finalize until approved
• Keep it simple
• Make clear choices
• choose options rather than allowing for several ways to do the same thing
• Exploit modularity
• independent layers
• Expect heterogeneity
• Avoid static options and parameters
• Look for a good design over a perfect one
• Be strict when sending and tolerant when receiving
• Thin about scalability
• Consider performance and cost
• ASes(Autonomous systems)
• connection of internetworks
• Tier 1 networks are ISPs
• following shows connections

• IP(Internet Protocol)
• glues together internet with similarities

The IP Version 4 Protocol

• Version field keeps track of which version of the protocol datagram belongs too
• IHL is provided to tell how long the header is
• Differentiated services field changed its meaning over the years
• originally type of service field
• Total length includes the entire datagram max length 65,535 bytes
• Identification field shows the host where the packet should go, where ti belongs to
• MF is more fragments all fragments except the last one have this bit sets, lets us know when all the fragments of a datagram has arrived
• Fragment offset tells where in the current packet the fragment belongs
• TtL is used to limit packet lifetimes
• counts number of hops
• protocol tells the transport process
• header checksum crc assumed to be 0 on arrival
• source/destination address is IP address
• options field is to allow subsequent version of the protocol to include information
• security tells how secret info is, military use
• strict source routing option gives complete path
• losse source routing gives packet ability to traverse the list of routers specified
• network measurement
• record route tells each router to append its ip address to options field
• timestamp option records the 32 bit timestamp

IP Addresses

• Prefix ip addresses are hierarchal, unlike ethernet
• dotted decimal notation
• subnet mask, prefixes described by their length

• Subnets
• ICANN(Internet Corporation for Assigned Names and Numbers)
• network numbers manager
• splitting prefix example

• CIDR - Classless InterDomain Routing
• routers must be able to determine path from each source to each destination
• tables growing larger and larger
• however, can group into subnets, route aggregation
• CIDR (Classless Inter- Domain Routing)
• router routes between same prefix routers

• when packet comes in routing table is scanned to see if destination lies within prefix
• possible multiple entries will match longest prefix used
• commercial routers use custom VLSI chips with algorithms embedded into hardware
• Classful and Special Addressing

• A allows for up to 128 networks with 16 million hosts
• B allows for up to 16,384 networks with 2 million hosts
• C allows for up to 2 million networks with 256 million hosts
• 3 bears problem, since B is the only network that makes sense for scalability for a company or organization
• Class D networks are being for multicast
• NAT - Network Address Translation
• IP adress are scarce
• dynamically assign IP address to a computer when it is on
• beginning to apply to home users subscribing to ADSL or internet over cable
• problem of running out of IP addresses, solution is to move to IPv6 but this is slowly occurring
• in the meantime we use NAT(Network Address Translation)
• assign each home or business with a single ip address
• within the customer network each computer gets a unique ip address
• these addresses are unavailable

• Operation of NAT
• before packets leave a customer it passes through a NAT box that converts the internal IP to the customer's true IP address

• how does provider send back to customer?
• observed that most IP packets carry TCP or UDP payloads
• contain source destination port
• ports indicate where the TCP connection begins and ends, so we can establish port to port processes rather than ip to ip processes
• ports 0-1023 are reserved, but 1024-65,535 are available for use, so each IP gets this many ports utilized to solve the mapping issue
• issues about using NAT
• breaks end to end connectivity as an outgoing packet is necessary before incoming packets can be allowed
• home user with NAT can make TCP/IP connections to remote web server, but remote user cannot make connections to game server on home network without NAT traversal techniques
• changes from connectionless to connection oriented in an odd way
• violates protocol layering, assumes TCP operational, if TCP is upgraded to a new style, NAT will fail
• processes are not required to use TCP or UDP, if new transport protocol used, NAT cannot handle
• FTP inserts IP addresses into the body of packet, but it cannot rewrite the IP addresses here

IP Version 6

• Goals
• support billions of hosts
• reduce size of routing table
• simplify protocol
• provide better security
• pay more attention to type of service
• aid multicasting by allowing scopes to be specified
• make it possible for hosts to roam
• allow protocol evolution
• permit old and new protocol to coexist until old can be phased out
• SIPP(Simple Internet Protocol Plus) became IPv6
• The Main IPv6 header

• differentiated services distinguishes class of packets
• flow label provides way for source and destination to mark groups of packets
• payload length tells how many bytes follow header
• next header can be optional extension headers, tells transport packets such as the handler where it should pass to next
• Hop limit is Time to live, same idea
• source address destination address with 16 byte addresses
• IPv4 are designated by double collons
• address space so large it won't be used efficiently but its unlikely to run out as there are 1000 IP addresses per square meter of the earth
• Extension Headers

• IPv6 allows for jumbo payload lengths that are used to transmit gigabyte sized packets across internet
• Controversies
• address length compromise
• hop limit field limited to 255 current technology
• remove the IPv4 checksum
• reasoning is that application would have transport layer checksum anyway so no point in doing this over again
• Deployment is the difficulty with IPv6 slow conversion in small islands of IPv6

Internet Control Protocols

• ICMP(Internet Control message protocol) message types are listed as follows

• Time exceeded error message used to create traceroute utility that finds the routers along the paths to a destination, send sequence of packets with counters to reach 0 each time along the packet
• ARP - The Address Resolution Protocol
• Data link layer NICs such as ethernet cards don't understand Internet Addresses
• host 1 outputs a broadcast packet on ethernet to see who owns an IP address
• host 2 responds with its ethernet address
• defined in RFC
• gratuitous ARP
• have every machine broadcast its mapping when configured, make update or entry in everyone's ARP, if error occurs resolved by network manager
• default gateway
• router where off network traffic is sent
• possible to send packet from host to host using proxies, so unable to give direct replies, but can set a router to forward to another network
• DHCP - The Dynamic Host Configuration Protocol
• when computer is started built in Ethernet or link layer address in NIC but no IP
• broadcasts request for IP DHCP DISCOVER packet, which much reach DHCP server
• then it tells the server where it is located
• IP address assignment may be only for a fixed period of time, leasing

Label Switching and MPLS

• MPLS (MultiProtocol Label Switching)
• connection oriented network
• adds a label in front of each packet and forwarding is based on label instead of destination address
• tag switching

• Label field holds the index
• QoS indicates class of service
• S refers to stacking multiple layers
• TtL is number of hops packet can live
• MPLS enhanced packet arrives at LSR(Label Switched Router)
• label is used as an index to determine outgoing line to use
• forwarding
• finds best match for a destination address
• switching
• uses a label taken from the packet as an index into a forwarding table
• simpler and faster but not universal definition
• most hosts don't understand MPLS
• LER(Label Edge Router)
• inspects destination IP address and other fields to see what path the MPLS packet should take
• Flows that belong to the same label are called FEC(Forwarding Equivalence Class)
• traditionally not possible to group several distinct forwarding paths
• can operate in multiple levels at once
• label forwarding tables set up by
• combining routing and connection setup protocols
• when router is booted checks to see which routes for final destination
• creates FECs for each label and pass them to their neighbors

OSPF - An Interior Gateway Routing Protocol

• OSPF (Open Shortest Path First)
• became standard in 1990
• draws on IS-IS(Intermediate System to Intermediate System)
• became ISO standard
• goals
• support variety of distance metrics
• dynamic algorithm
• based on type of service
• load balancing capable
• support for hierarchical systems
• security
• supports point to point links and and broadcast networks
• abstracts collection of networks routers and links into a directed graph in which each arc is assigned a weight in terms of distance/delay
• structure routes to hosts but not through them, only through networks such as LANS
• use a link state method to compute shortest path
• ECMP(Equal Cost MultiPath)
• remembers set of shortest path and splits traffic across them equally
• AS divide itself into numbered areas where an area is a network or set of continuous networks
• routers that lie in a router are called internal routers
• each AS has a backbone Area with backbone routers
• all areas are connected to the backbone
• each router is connected to two or more areas is called an area border router and is also part of the background
• if there is only one router out of an area it is called a stub area
• shortest path algorithms are used in an intra area sense and inter area sense
• find shortest path from area to area
• find shortest path from any host/node within an area to another within the area or from border router to any node in area
• exchange info between adjacent routers, but designates one router as the designated router to be adjacent to all other routers to exchange information so information not duplicated with one backup
• Message types listed in the following diagram

• BGP - The Exterior Gateway Routing Protocol
• BGP(Border Gateway Protocol)
• between ASes
• example policies gateway protocols can handle
• Do not carry commercial traffic on educational network
• don't send information from pentagon through iraq
• use TeliaSonera over Verizon
• don't use AT&T in Australia
• Apple traffic doesn't transit through Google
• ISP pay other ISPs to deliver packets, buy transit service
• interconnections called IXPs(Internet Exchange Points)
• ASes can do peering where they send each others traffic for free
• Multihoming
• company networks connected to multiple ISPs as backup
• Path Vector Protocol
• instead of maintaining routes, maintain path to next hop router and sequence of AS that route followed
• BGP communicates using TCP connections
• iBGP, eBGP internal or external BGP protocol
• internal every router at boundary learns all the routes seen by other boundary routers
• strategies
• routes via peered networks chosen in preference
• routes via shortest path chosen
• routes with lowest cost
• early exit or hot potato routing
• tends to make routes asymmetric

Internet Multicasting

• processes that send from one to a large number of viewers
• IP supports this due to range of IP addresses

• IGMP(Internet Group Management Protocol)
• every about once a minute hosts on LAN reports to a multicast router to identify which group they belong to
• PIM(Protocol Indpendent Multicast
• build spanning tree for multicast
• dense mode pruned reverse path forwarding used
• sparse mode similar to core based trees

Mobile IP

• goals
• each mobile host must be able to use home IP anywhere
• software changes to fixed host not permitted
• not permitted to change router software and tables
• packets should not make detours
• should not have overhead when mobile host is at home
• setup a home agent when roaming
• obtains a new IP address when in a foreign site
• packet for mobile arrives to home, it will tunnel to new site so mobile can send and reply using its home address instead of where it is at currently
• options to solve ip address issue
• create route to specific prefix at moving site, but too many sites possible
• change IP address of mobile, handles mobility at a higher level but breaks some applications whenever mobile moves
• mobility can be solved at link layer
• same as 802.11 wireless network, but degree of mobility is very limited
• IPv4 solution given in RFC 3344
• mobiles uses DHCP to get care of IP address at foreign location, finds an agent to get address from using ICMP
• tunneling achieved using proxy ARP to intercept packets
• Ingress filtering
• a security measure to discard addresses that are incorrect, but mobile will have foreign IPs so mobiles have to use care of address to tunnel packets to home location
• flying router on airplanes is different kind of mobility where the entire network is mobile

Back to ToC

Notes - Internetworking

The following are notes from Tanenbaum's Computer Networks 5th Edition.

• when multiple networks are connected together called internetwork or internet

How Networks Differ

• networks differ in many ways

• differences can be somewhat papered over
• gateway connecting networks can generate separate packets for each destination in lieu of better network support for multicasting
• QoS is difficult to ensure between multiple networks
• security difficult as well but encryption can be layered on top of one another

How Networks can be Connected

• build devices that translate packets, or add a layer of indirection and build a common layer on top of different networks
• TCP/IP protocol is foundation of modern internet
• Example
• 802.11, MPLS, and Ethernet networks want to be connected
• between MPLS and 802.11 
• virtual circuit must be set up because 802.11 is connectionless, MPLS is connection oriented
• between vc and ethernet
• packet may be too large to be carried, so packet must be divided into fragments

• routers that can handle these different protocols is called a multiprotocl router
• translates protocols or leave the connection for a higher protocol layer
• higher level requires all networks implement that application example TCP

Tunneling

• encapsulating an IPv6 packet through IPv4

• used to connect isolated hosts and networks
• overlay on the network
• limitation of tunnels is an advantage with VPNs (Virtual Private Networks)
• overlay used to provide a measure of security

Internetwork Routing

• two level routing algorithm
• within each network an intradomain, interior gateway protocol is used for routing
• across networks use interdomain or exterior gateway protocol
• often referred to as BGP(Border Gateway Protocol)
• AS(Autonomous System)
• network is operated independently
• i.e. ISP  network
• routing policy
• routing based on political agreements

Packet Fragmentation

• Limitations on packet size
• Hardware(size of a frame)
• Operating System(all buffers are 512 bytes)
• Protocols (the number of bits in packet length field)
• Compliance(to a standard or political agreement)
• Desire to reduce error induced retransmissions
• desire to prevent packets from occupying channel for a long time
• Max payload is 1500 bytes for ethernet
• 2272 bytes for 802.11
• Path MTU(Path Maximum transmission unit)
• know protocols from source to destination send packets small size
• MTU discovery, send packet length, if not possible return with try smaller size that is acceptable packet, until it reaches destination
• if MTU not possible break up into fragments
• first fragmentation strategy
• oversize packet arrives, router breaks it up, addressed to exit router where it is recombined
• end of packet bit provided because reassembly may not be in order
• second fragmentation strategy
• split up and recombine only at destination not at each transmitted router

 Back to Toc