bitstream

Technical characteristics

In 2003, software engineer Bram Cohen invented the BitTorrent protocol.

BitTorrent (BT for short) is a file distribution protocol, each downloader continuously uploads the downloaded data to other downloaders while downloading. In the FTP and HTTP protocols, while each downloader downloads the files he needs, there is no interaction between each downloader. When a large number of users access and download files on the server at the same time, due to the limitations of the processing capacity and bandwidth of the FTP server, the download speed will drop sharply, and some users may not be able to access the server. The BT protocol is different from the FTP protocol in that the more people who download, the faster the download speed, because each downloader provides the downloaded data to other downloaders to download, making full use of the user's upload bandwidth. Through certain strategies to ensure that the faster the upload speed, the faster the download speed. In a very short time, the BitTorrent protocol became a new revolutionary technology.

Implementation principle

Ordinary HTTP/FTP download uses TCP/IP protocol. BitTorrent protocol is a P2P file transfer protocol based on TCP/IP protocol, which is at the application layer of TCP/IP structure. The BitTorrent agreement itself also contains a lot of specific content agreements and expansion agreements, and is constantly expanding.

According to the BitTorrent agreement, the file publisher will generate a .torrent file based on the file to be published, that is, a seed file, also referred to as "seed" for short.

The .torrent file is essentially a text file, containing tracker information and file information. Tracker information is mainly the address of the Tracker server and the settings for the Tracker server that are used in BT download. The file information is generated based on the calculation of the target file, and the calculation result is encoded according to the B encoding rule in the BitTorrent protocol. Its main principle is to divide the file provided for download into blocks of equal size, and the block size must be an integer power of 2k (because it is a virtual block, each block file is not generated on the hard disk), and each block The index information and Hash verification code are written into the seed file (.torrent). Therefore, the torrent file (.torrent) is the "index" of the downloaded file.

Technology dependence

The development of bittorrent relies on peer-to-peer technology. Peer-to-Peer (P2P) research has always been the most important focus of well-known foreign universities, well-known enterprises and R&D institutions. It is even referred to as one of the four new technologies that change the development of the Internet by the American "Fortune" magazine, and is considered to be the key technology representing the future of wireless broadband Internet. It is now widely used in new technology and software projects.

P2P is the most popular technology on the Internet in recent years. It has developed rapidly in the fields of VoIP, downloading, streaming media, and coordination technology. It has been rated as one of the four major technologies affecting the Internet by Fortune Magazine. P2P technology embodies the most basic connotation of the Internet-free and free, and its main advantages are as follows: the nodes related to the search go up, the storage has the search; the equivalence is high: decentralization, the Internet returns to its true colors-contact and Transmission; strong scalability: user expansion is synchronized with resources, services, and systems; high robustness: service dispersion and adaptation, resistance to attacks, high fault tolerance; high cost performance: low P2P cost, strong storage and technical capabilities; load balancing: With distributed storage and technology, the entire network load is balanced.

In a P2P network, each participating node is both a server and a client, both an information provider and an information consumer. The purpose of P2P information retrieval is that any node in the network can submit a retrieval request, and then those nodes that retrieve the relevant information will respond to the request, and the local content will be routed to the relevant content directly in a peer-to-peer form. Transfer to the requesting node.

The retrieval process in the figure is divided into the following stages: When each node joins the network, it will index the content stored on this node to meet the purpose of local content retrieval. Then, according to some predetermined rule, some nodes are selected as their neighbors and added to the P2P network. The initiator P makes a retrieval request q, and sends q to its neighbor P. After receiving the q, it forwards it to other neighbor nodes in the network according to a certain strategy. In this way, q spreads throughout the network. If the node receiving the request q stores the corresponding content information, it will return the corresponding content.

How to locate resources in a large-scale distribution environment is a very challenging problem. The focus is on how to set up a P2P network and how to choose an effective resource request routing strategy in order to obtain more relevant query results with less message communication overhead and at the same time ensure a better service balance.

Download features

Unlike the regular download files, when you download BT, the addresses you start to link to are all files ending in .torrent. In fact, as long as you download this file, you can also download BT by running this file on this machine. The BT download links on the Internet are provided by the majority of users themselves, which makes the download information very wide and is not restricted by regular management personnel. [2] 

seed

No matter what kind of BT client program, the default settings do not limit the download speed and upload speed, this is because BT software will give priority to users with faster upload speed, that is, the faster the upload speed, the faster the download speed Fast, so if you use

Schematic diagram of BT principle

For broadband, don’t limit the upload speed when downloading.

After the download is complete, if the BT client program is not closed (for example, while running BT to provide upload services, while browsing the web, editing documents, etc.), then you will become a messenger to deliver the flame, that is, "seed" (seed). In other words, if a file is divided into 10 parts, but there is only one person who has Part 9, that is, only one seed, if this user disconnects or shuts down for some reason, then other users can only download to 90 %, it is the most distressing when downloading BT.

Think about the pain of "seed number is 0" when you download it. Compare your heart. Try not to close the BT program window immediately after the download is finished, and be a messenger of the torch.

Download note

To download the content of the file, the downloader needs to get the corresponding .torrent file first, and then use the BT client software to download it.

When downloading, the BT client first parses the .torrent file to get the Tracker address, and then connects to the Tracker server. The Tracker server responds to the downloader's request and provides the downloader's IPs of other downloaders (including the publisher). The downloader then connects to other downloaders. According to the .torrent file, the two parties tell each other that they already have blocks, and then exchange data that the other party does not have. At this time, no other server is required to participate, and the data traffic on a single line is dispersed, thus reducing the burden on the server.

Each time the downloader gets a block, he needs to calculate the comparison between the Hash verification code of the downloaded block and the .torrent file. If the block is the same, the block is correct. If the block is different, the block needs to be downloaded again. This regulation is to solve the problem of the accuracy of the downloaded content.

There is a problem

In general HTTP/FTP download, the published files are only on one or a few servers. There are too many people downloading. The bandwidth of the server is easily overwhelmed and becomes very slow. The characteristic of BitTorrent protocol download is that the more people who download, the more bandwidth they provide, the more seeds they will have, and the faster the download speed.

Some people turn off the download task after the download is complete and provide less data to other users. In order to avoid this behavior as much as possible, there is a super seed algorithm in the unofficial BitTorrent protocol. This algorithm allows the file publisher to publish the file in several steps. The publisher does not need to provide all the content of the file at once, but slowly opens up the proportion of the downloaded content to extend the download time. At this time, people with fast speeds must provide data to others because they have not finished downloading, and people with slow speeds have more opportunities to get data.

Network technology

DHT network technology has also been developed, making it possible to download without Tracker.

DHT is called Distributed Hash Table (Distributed Hash Table), which is a distributed storage method. Without the need for a server, each client is responsible for a small range of routing, and is responsible for storing a small part of the data, so as to achieve the addressing and storage of the entire DHT network. Using BT download software that supports this technology, users can download without connecting to Tracker, because the software will find other users who download the same file in the DHT network and communicate with it to start the download task.

Some software (Bit Genie) will also automatically search for seed resources through DHT to form a seed market.

In addition, the DHT algorithm used here is called Kademlia (also used in eMule, it is often called KAD, and the specific implementation protocol is different).

The benefits of this technology are very obvious, that is, it greatly reduces the burden of Tracker (not even needed). Users can establish communication more quickly (especially when they cannot connect to the Tracker).

Related concepts

Tracker: A server that collects downloader information and provides this information to other downloaders to connect downloaders with each other and transmit data.

Seed: refers to that all files in a download task are completely downloaded by a downloader, and the downloader becomes a seed at this time. The file published by the publisher itself is the original seed. Also refers to .torrent files.

Seeding: The act of the publisher providing the entire contents of the download task; the act of the downloader continuing to provide others with the download after the download is complete.

Features

BitTorrent is very helpful for the release of large documents and free software such as Linux and FreeBSD

. For the release of hundreds of MB or even several GB of files, such as Fedora's CD image format file, the use of BitTorrent can greatly reduce the server's data traffic and thus reduce the cost of publishing. In addition, when a new version of the software is generally released, the server is bound to be crowded. Using BitTorrent can also greatly reduce the burden on the server during busy hours.

History

In 2002, Bram Cohen made his first appearance at CodeCon and released his first BitTorrent BT software. It is written in Python and released under the MIT license.

legality

Introduction

The BT download method has caused widespread discussion in society.

Using BT to distribute copyright content for free will definitely damage the legal rights of copyright owners, but the benefits of distributing non-charged content are obvious to all. The focus of the debate is whether BT should be comprehensively banned as a result of this legislation and punish those who are engaged in BT downloads. But so far, the mainland of the People's Republic of China and Western European countries, such as Germany, still have no legal restrictions on BT. In Hong Kong, someone (nicknamed Emperor Gudou) has been arrested by the customs for releasing the seed of the movie. On October 24, 2005, the Hong Kong judiciary ruled that the infringement of the "Emperor of Confusion" was established and required immediate "custodial" for three months. Zeng Junhua, the head of Hong Kong's industrial and commercial department, and Tang Xianming, the "customs chief", welcomed the ruling and said that Hong Kong will not tolerate the existence of any infringements. At the same time, the government will also cooperate with businessmen to combat infringements at any time.

BitTorrent

(Referred to as BT, commonly known as BT download) is a multi-point download of open source P2P software, very convenient to use, just like a browser plug-in, very suitable for newly released popular downloads. Its characteristics are simply: the more people who download, the faster the speed. BitTorrent download tool software can be said to be a latest concept P2P download tool, which uses the principle of multi-point to multi-point, generally referred to as BT (BitTorrent) is what we call abnormal download. This software is quite special. Generally, we download files or software, most of which are downloaded from HTTP sites or FTP sites. If there are many downloaders at the same time, the speed will be much slower based on the factors of the server bandwidth, but the software is different. On the contrary, the more people who download at the same time, the faster your download speed, because it uses the multi-point to multi-point transmission principle.

Use

The BitTorrent file publishing system uses a tit_for_tat method to achieve Pareto effectiveness, and it has higher vitality than the currently known collaboration technology. This article will explain the purpose of BitTorrent and how to use economics to achieve this goal.

What BitTorrent is used for

When downloading a file via the HTTP protocol, all upload overhead is on the host. With BitTorrent, when multiple people download the same file at the same time, they also provide each other with partial file downloads for each other. In this way, the overhead of uploading is allocated to each downloader, and theoretically, an unlimited number of downloaders can be supported to download the same file.

Researchers have previously been looking for a practical technique to achieve this effect [3]. This technology has not been used in a large range, because the problem of logical sum is very difficult. If you only calculate which peers own which fragments of the file and to whom these fragments should be sent, it is difficult to incur only relatively small system overhead. The connection between Peers rarely exceeds a few hours, usually only a few minutes. Finally, there is a common problem, which is fairness.

We will explain how BitTorrent solves these problems well.

1.1. BitTorrent interface

BitTorrent's interface is probably the simplest. The user clicks on the hyperlink of the file that he wants to download, and then a standard "Save to" dialog box will pop up. After that, a download progress window appears. In this window, in addition to the download rate, an upload rate is also displayed. BT is very simple to use, making BT widely used.

1.2. deploy

The reason for deciding to adopt BitTorrent is because there are some documents to be published. The downloader uses BitTorrent because it is the only way for them to get the files they need. Downloaders often stop uploading for others as soon as they finish downloading, although it is polite to continue to provide others with uploads for a period of time after the BT client completes the download. The standard implementation is to keep the client uploading until the window is closed.

In a typical deployment, unfinished downloaders

A host is responsible for providing the original file, and the downloader downloads this file through BT. The downloader provides uploads for others while downloading, and finally, leaves the system.

Technical framework

2.1 Post content

To deploy BT, first put a file with the extension .torrent on a common web server. The .torrent file contains information about the file to be shared, including the file name, size, hash information of the file, and a url pointing to the tracker. Tracker is responsible for helping downloaders to obtain information from other downloaders. The tracker and the downloader use a very simple HTTP-based protocol to interact. The downloader tells the tracker the file to download, the port it uses, and similar information. The tracker tells the downloader that other downloaders download the same file. Contact information. Downloaders use this information to establish connections with each other. A downloader that has become a "seed" must first be started, it knows the complete file information. The bandwidth requirements for the tracker and web server are low, and the seed must send at least one complete copy of the original file.

Annotation:

The core idea of P2P is the concept of no server. Any downloader is both a client and a server.

When a downloader fetches a file from another person, it is called downloading, and when a file is provided to another person, it is called uploading (transfer).

In order to complete a deployment, at least one tracker and one seed are required. The so-called tracker is a server that is responsible for helping peers establish connections with each other. The seed is usually the first to register with the tracker, and then it begins to enter the loop, waiting for others to provide files, that is to say, the first seed is only responsible for uploading files. Once a peer has registered with the tracker, you can obtain seed information to establish a connection with the seed. Read the file from the seed. Since the original file is only owned by the seed, all said that the seed must upload at least a complete copy of the original file. If another peer joins, it can establish a connection with the seed and the previous peer at the same time, and then obtain files from both.

2.2 Peer-to-peer

All logical problems related to file downloads are resolved through interactions between peers. Some information about the download and upload rate is sent to the tracker, and the tracker collects this information for statistics. Tracker's responsibilities are strictly limited to "helping peers discover each other".

Although the tracker is the only way for peers to discover each other and the only place for peers to collaborate with each other, the standard tracker algorithm returns a random list of peers. Random graphs have very powerful features. Many peer selection algorithms eventually produce a power-law graph, which can be fragmented with a small amount of agitation. Note that the connections between peers are transmitted bidirectionally.

To keep track of what each peer has, BT cuts the file into fixed-size pieces (typically 256k in size). Each downloader must inform other peers about which pieces it has. In order to verify the integrity of the file, the hash information of each segment is calculated by the SHA1 algorithm and stored in the torrent file. Peers only notify other peers that it owns the fragment after checking the integrity of the fragment. Deleting code is a suggested technique to help file distribution, but this simpler method (both sharding) is also available.

Peers constantly download file fragments from the peers it can connect to. Of course, it cannot download anything from peers that are not connected to it. Even if the peers have established a connection, some of them do not contain the fragments they want, or they are not allowed to download. The strategy of not allowing other peers to download file fragments from it is called blocking choking, which will be discussed later. Other methods of file distribution usually use troublesome tree structures, and the uploading capacity of leaves has not been utilized. Simply let peers announce what it has that will cause less than 10% of the bandwidth expenditure, but it can reliably use all upload capabilities.

2.3 Pipelining

Application layer protocols built on top of TCP, such as BT, it is important that multiple requests should be sent at the same time to avoid delays between the sending of two fragments, because that would seriously affect the transmission rate. In order to achieve this goal, BT further divides each segment into sub-segments. The size of each sub-segment is generally 16k. At the same time, it keeps several requests (usually 5) being sent at the same time. The basis of the data selected by the pipeline operation (should refer to the number of requests sent at the same time, that is, 5 requests) is based on the fact that it can saturate most connections.

Annotation: That is to say, every time 5 requests are sent, and then after a while, 5 more requests are sent. Pipelining is widely used in HTTP protocol version 1.1.

2.4 Clip selection

Choosing a good sequence to download the clips is very important to improve performance. A poor segment selection algorithm may result in all segments being downloaded, or in another case, no segments are uploaded to other peers.

2.4.1 Strict priority

The first strategy of segment selection is: once a sub-segment of a certain segment is requested, then the remaining sub-segments of the segment are preferentially requested. In this way, a complete fragment can be obtained as quickly as possible

2.4.2 Least priority

For a downloader, when selecting the next segment to be downloaded, it usually selects the segment with the least number of its peers, which is the so-called "least priority". This technique ensures that each downloader has the pieces that its peers most want to get, so that uploading can begin once it is needed. This also ensures that the more common segments are placed in the final download, thereby reducing the possibility that a peer is currently providing uploads, and then there are no segments that are of interest to others.

Annotation:

That is to say, each peer preferentially selects the fewest fragments in the entire system to download, and the relatively many fragments in the system are downloaded later, so that the entire system tends to a better state . If you don’t use this algorithm, everyone will download the most fragments, then these fragments will be distributed more and more in the system, and the relatively few fragments in the system are still very few. Finally, some peers will No longer have other peers interested in, then the system has fewer and fewer participants, the performance of the entire system will decline.

In the BT system, the concept of economics is fully considered, and everywhere from the performance of the entire system, the more participants, the more optimized the system.

Information theory shows that unless the seed uploads all the fragments of the file, no downloader can complete the download of all files. If there is only one seed in a deployment, and the uploading ability of the seed is worse than most of its downloaders, then different downloaders download different fragments from the seed, the performance will become better, because, Repeated downloads waste the seed's chance to get more information. "Least priority" allows the downloader to download new clips only from the seed (that is, clips that are not available to other peers in the entire system), because the downloader can see the clips that have been uploaded by other peers.

In some deployments, the original seeds were finally closed for some reason, and the remaining downloaders were responsible for uploading. This obviously brings a risk: some downloaders do not own certain clips. "Least priority" also handles this situation well. By copying the fewest clips as soon as possible, this reduces the risk that the current peers will stop uploading.

2.4.3 Random first segment

An exception to "least priority" is at the beginning of the download. At this time, the downloader does not have any clips to upload, so you need to get a complete clip as soon as possible. The fewest pieces are usually only owned by a certain peer, so it may be slower to download than those pieces owned by multiple peers. Therefore, the first segment is randomly selected, and it is not switched to the "least priority" strategy until the first segment is downloaded.

2.4.4 Last stage mode

Sometimes, a fragment is requested from a very slow peer. In the middle of the download, this is not a problem, but it may potentially delay the completion of the download. In order to prevent this, in the final stage, the peer sends a request to all its peers for sub-segments of a certain segment. Once some sub-segments arrive, it will send a cancel message to other peers to cancel these sub-segments Requests to avoid wasting bandwidth. In fact, this method does not waste much bandwidth, and the end of the file has been downloaded very fast.

Blocking algorithm

BT does not allocate resources centrally. Each peer has its own responsibility to increase its download rate as much as possible. Peers download files from the peers it can connect to, and give equal upload rewards according to the download rate provided by the other party (you respect me, I respect you). For partners, provide upload services, for those who do not cooperate, block each other. Therefore, blocking is a temporary upload refusal strategy. Although the upload stops, the download continues. When the blocking stops, the connection does not need to be re-established.

The blocking algorithm does not belong to the technical part of the BT peer-to-peer protocol (referring to the interaction between peers), but it is necessary to improve performance. A good blocking algorithm should use all available resources to provide a consistent and reliable download rate for all downloaders, and appropriately penalize peers who only download but not upload.

3.1 Pareto effective

Pareto effective means that the resource allocation has reached a situation where any way to change the resource allocation cannot benefit some people without the damage of others. This state of resource allocation is called the "Pareto optimum" state, or "Pareto efficient"

In the computer field, seeking Pareto efficiency is a local optimization algorithm

BitTorrent's blocking algorithm attempts to achieve Pareto optimality in a tit-for-tat manner. (The original text is not easy to translate, I simplified it). Peers gave the same return to the peers who provided him with the upload service, the purpose is to hope that at any time there are several connections in the process of two-way transmission.

3.2 BitTorrent's blocking algorithm

From a technical level, each peer of BT has been kept clear of a fixed number of other peers (usually 4), so the question becomes which peers should be kept clear? This method enables TCP's congestion control performance to reliably saturate the upload capacity. (In other words, try to maximize the upload capacity of the entire system).

Strictly determine which peers should remain unblocked based on the current download rate. Surprisingly, calculating the current download rate is a big problem. The current implementation is essentially a poll every 20 seconds. The original algorithm is a total of a long time network transmission, but this method is very poor, because the bandwidth may change quickly due to resource availability or unavailability.

In order to avoid the waste of resources caused by frequent blocking and dredging peers, BT calculates which peer needs to be blocked every 10 seconds, and then maintains this state until the next 10 seconds. 10 seconds is enough for TCP to adjust its transmission performance to the maximum.

3.3. optimistic unchoking

If it is simply to provide uploads for the peers who provide the best download rate, then there is no way to find out whether those idle connections are better than those currently in use. To solve this problem, at any time, each peer has a connection called "optimistic unchoking". This connection is always kept unblocked regardless of its download rate. Every 30 seconds, recalculate which connection should be "optimistic unchoking". 30 seconds is enough to maximize the uploading capacity and the downloading capacity accordingly. This kind of thinking, which is relatively similar to tit for tat, is very great. "Optimistic unchoking" works very harmoniously with "Prisoner's Dilemma".

3.4. Against discrimination

In some cases, a peer may be blocked by all its peers. In this case, it will maintain a low download rate until it finds a better peer through "optimistic unchoking". In order to alleviate this problem, if after a period of time, a piece from a peer is not obtained, then the peer thinks that he is being "neglected" by the other party, so he no longer provides uploads for the other party unless the other party is "optimistic unchoking". This situation occurs frequently and will result in more than one concurrent "optimistic unchoking".

3.5 upload only

Once a peer has finished downloading, it can no longer use the download rate (because the download rate is already 0) to decide which peers to upload. The solution adopted is to prefer those peers that get a better upload rate from it. The reason is that the upload bandwidth can be used as much as possible.

Real experience

BitTorrent has not only been implemented for a long time, but has also been widely used. It provides hundreds of megabytes of file downloads for many concurrent downloaders. In the largest deployment known, there are more than 1,000 downloaders at the same time. The current bottleneck (not actually reached) seems to be the bandwidth of the trakcer. It (trakcer's bandwidth) occupies about one thousandth of the total bandwidth, and some small protocol extensions may make it down to one ten thousandth.